Tree traversal without recursion: the tree as a state machine (2007)
I've always found these kinds of tricks fascinating. There's all sorts of crazy things you can do to save some bytes here and there. One of my personal favorites is the XOR linked list[0]. It's a doubly linked list that uses as much memory as a singly linked list. It works by XORing the previous pointer with the next pointer. As you're doing a traversal you can compute the next pointer by making use of <i>next = prev XOR (prev XOR next)</i> giving you the address of the next node in the list.<p>Anyways, I did some digging into TAOCP. In section 2.3.1 Knuth mentions threaded binary trees[1]. They are trees that you can traverse without a stack <i>and do not use more memory than a regular binary tree</i>. This is compared to the method used in the post which requires you to store the parent pointers. The trick is that in a binary tree, lots of pointers are going to be null. Instead of storing null there, you can store a special value that provides information on how to traverse the tree. Indicating the difference between a regular pointer and one of these special values requires only a single bit. You can often store that bit within the pointer itself, requiring no additional space over a regular binary tree.<p>For a threaded binary tree, if the left child is null, you instead store the predecessor node. If the right child is null, you store the successor node. Finding the successor now becomes:<p><pre><code>    1) Check if the right child is null. If so the right child pointer points to the successor. We are done.
    2) Follow the right child pointer. Then keep following the left child pointer until the left child is null. This gives us the smallest value greater than the current value.
</code></pre>
One small advantage of threaded binary trees is you traverse the tree slightly less. If the right child is null, instead of traversing back up the tree as in the post, you can jump straight to the successor node.<p>[0] <a href="https://en.wikipedia.org/wiki/XOR_linked_list" rel="nofollow">https://en.wikipedia.org/wiki/XOR_linked_list</a><p>[1] <a href="https://en.wikipedia.org/wiki/Threaded_binary_tree" rel="nofollow">https://en.wikipedia.org/wiki/Threaded_binary_tree</a>