Ultimately the tree is going to turn into a real tree with branches and leaves so having it all magically get freed if someone does undef $tree would be great.

That will only happen if the whole tree is in that one scalar's memory block since no destructor is called.

The short answer is I don't want to have to write code that looks like the cookbook:

You should use the typemap to do that for you. I'm pretty sure Inline::C allows you to specify a typemap.