Hi all, This is my first posting to the Boost mailing list, so apologies in advance for any gaffes. I wanted to jump into the fray a bit on the tree container discussion with a couple little thoughts I had on the topic. There's been some excellent points made, reviewing the thread thus far, about separating the concerns of tree structure from tree iteration. I agree that it's very appropriate to consider designing the fundamental structure and operations on a tree a distinct exercise from designing how the data might be accessed, traversed or mutated by standard algorithms. Talking first in terms of concepts such as TreeContainer, which behave similarly to (or refine) the existing standard library Container, seems like the right approach. But there has also been some mention of more refined concepts such as AVL Tree, Red-Black Tree, Splay Tree, BTree, etc. which have some intrinsic algorithmic properties that distinguish them from what I'd call a "basic" tree for lack of a better term. I believe that an AVL tree, for example, is not actually a refinement of the basic tree concept, because you can not treat an AVL tree polymorphically as a basic tree. Inserting into one of these types of specialized trees, for example, may invalidate iterators or violate other ordering assumptions that are safe to make in a basic tree. I'm picturing a particularly hairy instance where you have iterators marking a range in, say, a red-black tree, and you call std::transform() on that range in-place. In other words, I think the only tree structures that are appropriate to consider are the basic TreeContainer and strict refinements thereof. Taking my own argument to an extreme, I'm not even entirely convinced that binary or k-ary trees should be considered, since they aren't strictly substitutable for basic trees... That aside, the real idea I wanted to offer was this: If we want to provide the type of behavior that one of these various self-balancing search trees, etc. would offer (which I certainly think we should), it should take much the same form as the heap algorithms present in the standard library do today. The operations push_heap(), pop_heap(), make_heap(), sort_heap() and is_heap() operate with typical, characteristic cleverness on a sequential range of RandomAccessIterators, imposing an ordering more specific than that offered by the RandomAccessContainer storing the data. Similarly, operations such as is_k_ary_tree(int), is_avl_tree(), avl_balance(), etc. would serve to impose and maintain a useful, more specific structure on top of TreeContainer, and would avoid having to make a messy hierarchy of structural concepts. So, this is all just to say: if we adopt the approach of further separating the concern of specialized tree structures, then I believe the exercise of formulating good concepts for basic tree structures becomes simpler. Furthermore, I'm guessing that also makes things easier when we do get to the step of worrying about standard iterators and interoperability with standard library algorithms. Hope this is a useful contribution! Cheers, dr