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.

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

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:

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.

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

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.

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.

Com­plete Code:

Out­put:

```1  2  4  10  12  13  15
```

You may also like...

• Wang Shuhao

This is for BST.