This post will explore a threaded binary tree and convert a normal binary tree into a single-threaded binary tree.
We know that a recursive inorder tree traversal algorithm uses stack space proportional to a tree’s height. For a balanced tree containing n elements, the algorithm takes O(log(n)) space but, for a skewed tree, this goes up to O(n) . The iterative algorithm for inorder traversal exists, but it also takes extra space for the stack.
One feasible solution to this problem is a threaded binary tree that allows fast inorder tree traversal without extra space. In a single-threaded binary tree, all null right child pointers in a binary tree point to the in-order successor of the node (if it exists). Now given a pointer to a node in a threaded tree, it is possible to find its inorder successor cheaply.
Please note that another variant of a threaded binary tree, called double–threaded binary tree having null left child pointers pointing to the inorder predecessor of the node (if it exists) along with null right child pointers pointing to the inorder successor.
Convert a Binary Tree into a Threaded Binary Tree:
To convert a binary tree into a threaded binary tree, point all null right child pointers to that node’s inorder successor. The idea is to perform an inorder traversal of the binary tree and pass information about the previously visited node along with the node. If the current node has a null right child, set the right child of its previous node to point to it.
Also maintain a boolean field in each Node that is true wherever the right pointer of a node points to its inorder successor. This field is useful while traversing the threaded binary tree to find an inorder successor if the current node has a threaded link.
Now let’s construct a threaded binary tree out of a normal binary tree, in C++, Java, and Python: