Except they implemented it wrong. You are supposed to leave gaps in the numbering to add new nodes. If you use consecutive numbers then inserting a node require

Except they implemented it wrong. You are supposed to leave gaps in the numbering to add new nodes. If you use consecutive numbers then inserting a node requires renumbering all consecutive nodes. When I was faced with this problem, I used a dynamically sized bit vector field as an id and indexed it lexicographically. When a node is inserted, it's assigned the id of its parent appended with a 0 or 1, depending on its relationship to the parent. Thus, ids are unlimited and never have to be reassigned. Selecting a subtree is just a single range search. For a non-binary tree, a vector of some other type can be used. I got the idea from this: http://en.wikipedia.org/wiki/Surreal_numbers http://en.wikipedia.org/wiki/Surreal_numbers