Interesting... now that I think of it, it's not necessary for a node to know how high it is, because that information is available in the traversal algorithm (t

Interesting... now that I think of it, it's not necessary for a node to know how high it is, because that information is available in the traversal algorithm (the node is guaranteed to be encountered at the level which represents its height). Using a log-2 dice roll (as the algorithm specifies), you will get nodes with an average height of 2, and with only forward pointers, that does work out to 2 pointers per node. I may have to revisit my implementation and do it "right".