Convert a Binary Tree to Threaded binary tree | Set 2 (Efficient)

Idea of Threaded Binary Tree is to make inorder traversal faster and do it without stack and without recursion. In a simple threaded binary tree, the NULL right pointers are used to store inorder successor. Where-ever a right pointer is NULL, it is used to store inorder successor.

Following diagram shows an example Single Threaded Binary Tree. The dotted lines represent threads.

Following is structure of single threaded binary tree.

 struct Node {     int key;     Node *left, *right;        // Used to indicate whether the right pointer is a normal right      // pointer or a pointer to inorder successor.     bool isThreaded;  };

How to convert a Given Binary Tree to Threaded Binary Tree?
We have discussed a Queue based solution here. In this post, a space efficient solution is discussed that doesn’t require queue.

The idea is based on the fact that we link from inorder predecessor to a node. We link those inorder predecessor which lie in subtree of node. So we find inorder predecessor of a node if its left is not NULL. Inorder predecessor of a node (whose left is NULL) is rightmost node in left child. Once we find the predecessor, we link a thread from it to current node.
Following is the implementation of the above idea.

C#

Output:

Inorder traversal of creeated threaded tree is
4 2 5 1 6 3 7

This algorithm works in O(n) time complexity and O(1) space other than function call stack.