My opinion is that the cleanest way of dealing with this is (more-or-less) your suggestion to let a Tree instance have an optional equality function attribute.