Since a binary tree with $N$ nodes has $N+1$ NULL pointers (across leaves), half the space allocated in a binary search tree for pointer information is wasted. Suppose that if a node has a NULL left child, we make its left child point to its in-order predecessor, and if a node has a NULL right child, we make its right child point to its in-order successor. This is known as a threaded tree and the extra pointers are called threads. In what way this implementation helpful? Can any one provide useful information.

• What do you think? We expect you to do some basic research and work on a problem a little yourself before posting here. – David Richerby Jan 19 '15 at 10:23
• Try searching for the term. – Raphael Jan 19 '15 at 13:23

Threaded trees make it possible to perform inorder-traversal without the use of stack or recursion. The threads make it possible to back-up to higher levels. Thre is a catch: we should be able to distinguish threads from ordinary links, and the obvious way to do that is to use a bit for each link, to mark the threads. However, there are (very inefficient) techniques to check threads vs. edges in unmarked trees.

• There is no real advantage for traversal in space or time, in terms of $\Theta$. Threading is useful if you need the previous/next in-order node of a distinguished node and you don't have $\Theta(\operatorname{height}(T))$ time. – Raphael Jan 19 '15 at 13:24

Threaded trees make in-order tree traversal a little faster, because you have guaranteed O(1) time to access the next node. This is opposed to a regular binary tree where it would take O(lg n) time, because you have to "climb" up the tree and then back down.

The trade off is that you're opting to determine what the next in-order node is when you insert into the tree, rather than when you're doing the traversal.

• If you implement the traversal recursively, there's not runtime penalty without threading. Also, you assume logarithmic tree height which is not true for all trees. – Raphael Jan 19 '15 at 13:23
• If you implement the traversal recursively, you are not guaranteed constant time to access the next in-order node. It will take time proportional to log n (big O notation denotes proportionate runtime, not exact runtime). – Ben Weintraub Jan 20 '15 at 1:50
• Picture a binary search tree, now think about the case where you access a leaf node that happens to be the right child of its parent. The next in-order node will take a minimum two "jumps" to access (our leaf's "grandfather" node), and possibly more if the grandfather node (and any of its ancestors) is smaller than the leaf. – Ben Weintraub Jan 20 '15 at 1:59