Convert Binary Tree into Threaded Binary Tree

Objec­tive: Given a binary tree write an algo­rithm to con­vert it into threaded binary tree.

Note: Tree node has extra Boolean field to be used.

Convert Binary Tree into Threaded Binary Tree example

In ear­lier arti­cle “Intro­duc­tion to Threaded Binary Tree” we have seen what is threaded binary tree, types of it and what advan­tages it has over nor­mal binary tree. In this arti­cle we will see how to con­vert exist­ing binary tree to threaded binary tree. we will con­vert it to sin­gle threaded binary tree.

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

Sin­gle Threaded: each node is threaded towards either the in-order pre­de­ces­sor or suc­ces­sor (left or right) means all right null point­ers will point to inorder suc­ces­sor OR all left null point­ers will point to inorder predecessor.

So in this arti­cle we will put all right null point­ers to it’s inorder successor.

Approach:

Solu­tion 1: we can do the inorder tra­ver­sal and store it in some queue. Do another inorder tra­ver­sal and where ever you find a node whose right ref­er­ence is NULL , take the front ele­ment from the queue and make it the right of the cur­rent node.  (Ref­er­ence: http://www.geeksforgeeks.org/convert-binary-tree-threaded-binary-tree/)

Bet­ter Solution:

The prob­lem with the ear­lier solu­tion is it’s using the extra space for stor­ing the inorder tra­ver­sal and using two traversals.

Now we will see the solu­tion which will con­vert binary tree into threaded binary tree in one sin­gle tra­ver­sal with no extra space required.

  • Do the reverse inorder tra­ver­sal, means visit right child first.
  • In recur­sive call, pass addi­tional para­me­ter, the node vis­ited previously.
  • when­ever you will find a node whose right pointer is NULL and pre­vi­ous vis­ited node is not NULL then make the right of node points to pre­vi­ous vis­ited node and mark the boolean right­Threaded as true.
  • Impor­tant point is when­ever mak­ing a recur­sive call to right sub­tree, do not change the pre­vi­ous vis­ited not and when mak­ing a recur­sive call to left sub­tree then pass the actual pre­vi­ous vis­ited node. see the image below

Convert Binary Tree into Threaded Binary Tree

Read the com­plete code for bet­ter understanding.

Com­plete Code:

Out­put:

Inorder Traversal:
1 5 7 10 12 15 20

You may also like...