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

Double Threaded Binary Tree Complete Implementation

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 the com­plete imple­men­ta­tion of dou­ble threaded binary tree. ( Click here to read about “single threaded binary tree”)

Double threaded binary tree

Image Source : http://web.eecs.umich.edu/~akamil/teaching/su02/080802.ppt

Dou­ble threaded: each node is threaded towards both the in-order pre­de­ces­sor and suc­ces­sor (left and right) means all right null point­ers will point to inorder suc­ces­sor AND all left null point­ers will point to inorder predecessor.

Imple­men­ta­tion:

Let’s see how the Node struc­ture will look like

class Node {
   int data;
   int leftBit;
   int rightBit;
   Node left;
   Node right;

   public Node(int data) {
      this.data = data;
   }
}

If you notice we have two extra fields in the node than reg­u­lar binary tree node. left­Bit and right­Bit. Let’s see what these fields represent.

leftBit=0 left ref­er­ence points to the inorder predecessor
leftBit=1 left ref­er­ence points to the left child
rightBit=0 right ref­er­ence points to the inorder successor
righBit=1 right ref­er­ence points to the right child

Let’s see why do we need these fields and why do we need a dummy node when If we try to con­vert the nor­mal binary tree to threaded binary

Need of dummy root

Now if you see the pic­ture above , there are two ref­er­ences left most ref­er­ence and right most ref­er­ence point­ers has nowhere to point to.

 Need of a Dummy Node: As we saw that ref­er­ences left most ref­er­ence and right most ref­er­ence point­ers has nowhere to point to so we need a dummy node and this node will always present  even when tree is empty.

In this dummy node we will put right­Bit = 1 and its right child will point to it self and left­Bit = 0, so we will con­struct the threaded tree as the left child of dummy node.

Let’s see how the dummy node will look like:

Dummy Node

Now we will see how this dummy node will solve our prob­lem of ref­er­ences left most ref­er­ence and right most ref­er­ence point­ers has nowhere to point to.

Double Threaded binary tree with dummy node

Dou­ble Threaded binary tree with dummy node

Now we will see the some oper­a­tions in dou­ble threaded binary tree.

Insert():

The insert oper­a­tion will be quite sim­i­lar to Insert oper­a­tion in Binary search tree with few modifications.

  1. To insert a node our first task is to find the place to insert the node.
  2. First check if tree is empty, means tree has just dummy node then then insert the new node into left sub­tree of the dummy node.
  3. If tree is not empty then find the place to insert the node, just like in nor­mal BST.
  4. If new node is smaller than or equal to cur­rent node then check if left­Bit =0, if yes then we have found the place to insert the node, it will be in the left of the sub­tree and if leftBit=1 then go left.
  5. If new node is greater than cur­rent node then check if right­Bit =0, if yes then we have found the place to insert the node, it will be in the right of the sub­tree and if rightBit=1 then go right.
  6. Repeat step 4 and 5 till the place to be inserted is not found.
  7. Once decided where the node will be inserted, next task would be to insert the node. first we will see how the node will be inserted as left child.
n.left = current.left;
current.left = n;
n.leftBit = current.leftBit;
current.leftBit = 1;
n.right = current;

see the image below for bet­ter understanding

Insert the node into left subtree

  1. To insert the node as right child.
n.right = current.right;
current.right = n;
n.rightBit = current.rightBit;
current.rightBit = 1;
n.left = current;

see the image below for bet­ter understanding.

Insert the node into right subtree

Tra­verse():
Now we will see how to tra­verse in the dou­ble threaded binary tree, we do not need a recur­sion to do that which means it won’t require stack, it will be done n one sin­gle tra­ver­sal in O(n).
Start­ing from left most node in the tree, keep tra­vers­ing the inorder suc­ces­sor and print it.(click here to read more about inorder suc­ces­sor in a tree).
See the image below for more understanding.

traverse in the double threaded binary tree

Com­plete Code:


Out­put:

1  2  4  10  12  13  15

You may also like...