Threaded binary search tree implementation

What are threaded binary search tree?

Threaded binary search tree is BST in which all right pointers of node which point to NULL are changed and made to point to inorder successor current node (These are called as single threaded trees). In completely threaded tree (or double threaded trees), left pointer of node which points to NULL is made to point to inorder predecessor of current node if inorder predecessor exists. Refer inorder successor and predecessor to understand more on inorder predecessor and successor. Example of threaded binary search tree is as below

Threaded binary search tree
Single threaded tree
double threaded binary search tree
double threaded tree

Now, there is small thing needs to be taken care of. A right or left pointer can have now two meanings : One that it points to next real node, second it is pointing inorder successor or predecessor of node, that means it is creating a thread. To store this information, we added a bool in each node, which indicates whether pointer is real or thread.

Structure of node for threaded binary search becomes :

Why do we need Threaded binary search trees ?

First, to make use of already allocated memory, like all pointers in leaf nodes of BST is always pointing to NULL. Number of pointers used at leaf level is maximum, we can use them to connect to some real information and then use this information to optimize some operation on BST.

One example which comes to mind is inorder traversal of BST without using stack and recursion. If we have inorder successor information stored in BST using thread, this is a very simple and efficient traversal with no extra explicit or implicit space used.

How to created a threaded BST?

As mentioned earlier, node definition of tree changes a bit to figure out if the right pointer is thread or pointing to genuine right child of node.

First, let’s if we have already a tree and we want to convert it into single threaded tree. Make sure node already has boolean in it. Later, we will see how to create a threaded BST from scratch.

To convert a BST to threaded binary tree, we will first do inorder traversal of tree and store all nodes in queue. Next, we will again do inorder traversal and whichever node does not have right child link it to node at front of queue. Also, take care that node is take out of queue when it is processed. Implementation is quite simple.

Threaded binary search tree implementation

This method has couple of drawback which are worth talking about. First, each very apparently uses extra memory to store all nodes. Second, it requires two traversals of tree.

In next post, we will see how to optimize this method so as to created threaded binary search tree in single traversal and also, we will see how can we do inorder traversal of BST without using stack and recursion.

Please share if there is something is wrong or missing. Sharing is caring.