I implemented this in the core data structures for IE5. We were very memory constrained as we had to run on Win95 machines with something like 12MB of RAM. I was counting bits.

The base level of the tree wasn't really a node DOM but rather a stream of document events (start element, text, end element, etc). We put these in a binary tree that was balanced as a splay tree. To drive memory usage down I reduced the {parent, left, right} pointers down to {child, next, left_child_bit, next_is_parent_bit}. 'child' pointed to the the first child. I knew if it was the left or the right child based on the left_child_bit. 'next' pointed either to the sibling or the parent, depending on the 'next_is_parent_bit'. However, to really realize the savings, I needed to hide these bits in the pointers themselves.

Other tricks that we used to save memory:

1) Put rare data into a hash table indexed off of the 'this' pointer of the object. Have a bit to indicate if it was there or not. We called these lookaside pointers.

2) Embed objects in other objects to save pointers back and forth. The embedded object would do math on its this pointer (based on bits for which embedded member it is) to get the this pointer of the parent object.

I'm not sure, but I suspect that one of the reasons I think that current IE is slower now than it should be is that a lot of these optimizations are no longer necessary and cause more problems than they solve.