If I would have to implement it then I think I would allow these things: (I leave it up to you to decide wheter they are good or bad)

First one, is the one that is suggested: see if the nodes define a compare/equal method of some sort. (check it with the ISA->can method)

Second one, allow a coderef (anonyoums or not, that's irrelevant) to be passed to the new method (when you're creating the object). (You could also allow a (different) coderef to be passed to the add_node routine)

Third one, when neither the first nor the second is available use '==' or 'eq' or both. (Perhaps there is someone out there that already created a Node class, and has overridden ==/eq and wants to use your Tree class.)