# Convert Binary Tree into Threaded Binary Tree

Objective: Given a binary tree write an algorithm to convert it into threaded binary tree.

Note: Tree node has extra Boolean field to be used. In earlier article “Introduction to Threaded Binary Tree” we have seen what is threaded binary tree, types of it and what advantages it has over normal binary tree. In this article we will see how to convert existing binary tree to threaded binary tree. we will convert it to single threaded binary tree.

• Binary trees have a lot of wasted space: the leaf nodes each have 2 null pointers. We can use these pointers to help us in inorder traversals.
• Threaded binary tree makes the tree traversal faster since we do not need stack or recursion for traversal

Single Threaded: each node is threaded towards either the in-order predecessor or successor (left or right) means all right null pointers will point to inorder successor OR all left null pointers will point to inorder predecessor.

So in this article we will put all right null pointers to it’s inorder successor.

Approach:

Solution 1: we can do the inorder traversal and store it in some queue. Do another inorder traversal and where ever you find a node whose right reference is NULL , take the front element from the queue and make it the right of the current node.  (Reference: http://www.geeksforgeeks.org/convert-binary-tree-threaded-binary-tree/)

Better Solution:

The problem with the earlier solution is it’s using the extra space for storing the inorder traversal and using two traversals.

Now we will see the solution which will convert binary tree into threaded binary tree in one single traversal with no extra space required.

• Do the reverse inorder traversal, means visit right child first.
• In recursive call, pass additional parameter, the node visited previously.
• whenever you will find a node whose right pointer is NULL and previous visited node is not NULL then make the right of node points to previous visited node and mark the boolean rightThreaded as true.
• Important point is whenever making a recursive call to right subtree, do not change the previous visited not and when making a recursive call to left subtree then pass the actual previous visited node. see the image below Read the complete code and try it in our IDE for better understanding.

Complete Code:

 public class BSTtoTBST { public static Node root; public void convert(Node root){ inorder(root, null); } public void inorder(Node root, Node previous){ if(root==null){ return; }else{ inorder(root.right, previous); if(root.right==null && previous!=null){ root.right = previous; root.rightThread=true; } inorder(root.left, root); } } public void print(Node root){ //first go to most left node Node current = leftMostNode(root); //now travel using right pointers while(current!=null){ System.out.print(" " + current.data); //check if node has a right thread if(current.rightThread) current = current.right; else // else go to left most node in the right subtree current = leftMostNode(current.right); } System.out.println(); } public Node leftMostNode(Node node){ if(node==null){ return null; }else{ while(node.left!=null){ node = node.left; } return node; } } public static void main(String[] args) { root = new Node(10); root.left = new Node(5); root.right = new Node(15); root.left.left = new Node(1); root.left.right = new Node(7); root.right.left = new Node(12); root.right.right = new Node(20); BSTtoTBST bsTtoTBST = new BSTtoTBST(); bsTtoTBST.convert(root); System.out.println("Inorder Traversal: "); bsTtoTBST.print(root); } } class Node{ Node left; Node right; int data; boolean rightThread; public Node(int data){ this.data = data; rightThread = false; } }

view raw
BSTtoTBST.java
hosted with ❤ by GitHub

Output:

```Inorder Traversal:
1 5 7 10 12 15 20
```

This site uses Akismet to reduce spam. Learn how your comment data is processed.