To answer your question, I usually use nested arrayrefs when I implement trees in basic Perl data structures and the second of the two "complex relational" structures when I'm storing them in databases.

FWIW, a few months ago I was looking for a good Tree::* module that I could quickly adapt for a project I was working on. I looked at your Tree::Simple and ultimately decided against it and went with Tree::MultiNode instead. I just liked Tree::MultiNode's API better, although I would say Tree::Simple looks like it is the more mature of the two.I admit that what initially turned me off on Tree::Simple was the use of StudlyCaps for method names, but I was also attracted to Tree::MultiNode since it is an implementation of Sedgewick's algorithms which I was familiar with. Anyway, I just re-read the Tree::Simple POD on search.cpan.org, and I noticed that you compare and contrast Tree::Simple to every other Tree::* module out there except Tree::MultiNode. Sorry to go off on this tangent...