You can download the complete program from here Binary trees need to be traversed using recursion. All the three methods of traversal - inorder, preorder and post order methods employ recursion. Recursion needs stack storage. In cases where the tree is highly unbalanced, the cost on this traversal would be high. It would be nice where one could traverse a binary tree without using recursion. That is where a threaded tree comes into picture. This utilizes the pointers which are wasted on leaf nodes and uses these to save threads pointing to inorder successor or inorder predecessor. In the diagram above, node A does not have right child. Instead of NULL, a link to B is stored in A->right. Remember that B is the inorder successor of A. Similarly C does not have child nodes. So it has link to predecessor B as left thread and link to D as right thread. Only A has left link as NULL because A has no predecessor. And I has no successor, so it has right link as NULL. ...