Since the interest level in a generic tree library seems to be high, below is a link to an incomplete tree library/type constructor framework I have been tinkering with. It, perhaps foolishly, tries to present the building blocks for the construction of a large set of different tree types with different balancing and book-keeping requirements. Keep in mind it is not complete, some of the balancing schemes need to be checked, it has no workarounds for broken compilers and for the most part only basic/range insert have been implemented (erase is just a placeholder) http://24.221.194.82:8080/src/trees/index.html There are a number of meta programming techniques used in the library, including execute_if which i brought up in a separate thread, the techniques link via the above link describes a few of them (template parameter mapping, execute_if etc). http://24.221.194.82:8080/src/tc/index.html The above is a start at defining some of the terms and concepts used in type constructors/builders/computers, once meaningful terms are agreed upon the tree documentation will change to use the new terms. Stroustrup on a generic binary tree library: Matt Austern, Bjarne Stroustrup, Mikkel Thorup, and John Wilkinson: Untangling the Balancing and Searching of Balanced Binary Search Trees. Software - Practice & Experience. Vol 33, Issue13. October 2003 (google only has a link to the example code in this paper) Stroustrup on binary tree iterators: http://portal.acm.org/citation.cfm?id=268114 Feedback is appreciated, -Jeff Mirwaisi