Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

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...