Hi Dave,
My personal intuition, not at all tested on real experience, is that you want to make the nodes as thin as possible.
Agreed.
The only reason I can think of to justify a dynamically sized node is to construct a tree where the size of the nodes varies considerably.
Well, the concepts I'm hoping to support, roughly speaking, are binary trees (a node contains at most 2 children), k-ary trees (a node contains at most k children), and trees with no limit on the number of children per node. To say that users who want the third type of tree should just use boost::graph, or that a trie shouldn't be implemented as a tree, seems draconic to me. I think the tree concept should be general-purpose enough to encompass these uses, even if it's embodied by multiple implementations with different space/time tradeoffs. But the question I really wanted to ask in response to your thoughts was, how big do you think is too big? The way I'd think of implementing a node in a binary tree is something like: struct node { node* parent_; node* first_; node* second_; T* value_; }; In a k-ary tree, it would be: struct node { node* parent_; node* children_; // allocated using allocator::allocate(k, 0); T* value_; }; And in a general-purpose tree, it would be: struct node { node* parent_; node* first_child_; node* last_child_; node* prev_sibling_; node* next_sibling_; T* value_; }; Would you consider five pointers to be too much? Cheers, dr