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

• 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