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 the complete implementation of double threaded binary tree. ( Click here to read about “single threaded binary tree“)
Image Source : http://web.eecs.umich.edu/~akamil/teaching/su02/080802.ppt
Double threaded: each node is threaded towards both the in-order predecessor and successor (left and right) means all right null pointers will point to inorder successor AND all left null pointers will point to inorder predecessor.
Implementation:
Let’s see how the Node structure 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 regular binary tree node. leftBit and rightBit. Let’s see what these fields represent.
leftBit=0 | left reference points to the inorder predecessor |
leftBit=1 | left reference points to the left child |
rightBit=0 | right reference points to the inorder successor |
righBit=1 | right reference 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 convert the normal binary tree to threaded binary
Now if you see the picture above , there are two references left most reference and right most reference pointers has nowhere to point to.
Need of a Dummy Node: As we saw that references left most reference and right most reference pointers 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 rightBit = 1 and its right child will point to it self and leftBit = 0, so we will construct 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 problem of references left most reference and right most reference pointers has nowhere to point to.
Now we will see the some operations in double threaded binary tree.
Insert():
The insert operation will be quite similar to Insert operation in Binary search tree with few modifications.
- To insert a node our first task is to find the place to insert the node.
- First check if tree is empty, means tree has just dummy node then then insert the new node into left subtree of the dummy node.
- If tree is not empty then find the place to insert the node, just like in normal BST.
- If new node is smaller than or equal to current node then check if leftBit =0, if yes then we have found the place to insert the node, it will be in the left of the subtree and if leftBit=1 then go left.
- If new node is greater than current node then check if rightBit =0, if yes then we have found the place to insert the node, it will be in the right of the subtree and if rightBit=1 then go right.
- Repeat step 4 and 5 till the place to be inserted is not found.
- 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 better understanding
- 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 better understanding.
Traverse():
Now we will see how to traverse in the double threaded binary tree, we do not need a recursion to do that which means it won’t require stack, it will be done n one single traversal in O(n).
Starting from left most node in the tree, keep traversing the inorder successor and print it.(click here to read more about inorder successor in a tree).
See the image below for more understanding.
Complete Code:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
public class DoubleThreadedBinaryTree { | |
public static Node root; | |
public static boolean directionLeft; | |
public static boolean directionRight; | |
public DoubleThreadedBinaryTree() { | |
//create the dummy node | |
root = new Node(Integer.MAX_VALUE); | |
root.leftBit = 0; | |
root.rightBit = 1; | |
root.left = root.right = root; | |
} | |
public void insert(int data) { | |
Node n = new Node(data); | |
//check if new node is going to be first actual node in the tree. | |
if (root == root.left && root.right == root) { | |
n.left = root; | |
root.left = n; | |
n.leftBit = root.leftBit; | |
root.leftBit = 1; | |
n.right = root; | |
} else { | |
Node current = root.left; | |
while (true) { | |
if (current.data > n.data) { | |
if (current.leftBit == 0) { | |
//node will be added as left child | |
directionLeft = true; | |
directionRight = false; | |
break; | |
} else { | |
current = current.left; | |
} | |
} else { | |
if (current.rightBit == 0) { | |
//node will be added as right child | |
directionLeft = false; | |
directionRight = true; | |
break; | |
} else { | |
current = current.right; | |
} | |
} | |
} | |
if (directionLeft) { | |
//add the node as left child | |
n.left = current.left; | |
current.left = n; | |
n.leftBit = current.leftBit; | |
current.leftBit = 1; | |
n.right = current; | |
} else if (directionRight) { | |
//add the node as right child | |
n.right = current.right; | |
current.right = n; | |
n.rightBit = current.rightBit; | |
current.rightBit = 1; | |
n.left = current; | |
} | |
} | |
} | |
public void inorder() { | |
//start from the left child of the dummy node | |
Node current = root.left; | |
//go to the left most node | |
while (current.leftBit == 1) { | |
current = current.left; | |
} | |
//now keep traversing the next inorder successor and print it | |
while (current != root) { | |
System.out.print(" " + current.data); | |
current = findNextInorder(current); | |
} | |
} | |
public Node findNextInorder(Node current) { | |
//if rightBit of current node is 0 means current node does not | |
//have right child so use the right pointer to move to its | |
// inorder successor. | |
if (current.rightBit == 0) { | |
return current.right; | |
} | |
//if //if rightBit of current node is 0 means current node does | |
//have right child so go to the left most node in right sub tree. | |
current = current.right; | |
while (current.leftBit != 0) { | |
current = current.left; | |
} | |
return current; | |
} | |
public static void main(String args[]){ | |
DoubleThreadedBinaryTree i = new DoubleThreadedBinaryTree(); | |
i.insert(10); | |
i.insert(12); | |
i.insert(15); | |
i.insert(2); | |
i.insert(13); | |
i.insert(1); | |
i.insert(4); | |
i.inorder(); | |
} | |
} | |
class Node { | |
int data; | |
int leftBit; | |
int rightBit; | |
Node left; | |
Node right; | |
public Node(int data) { | |
this.data = data; | |
} | |
} |
Output:
1 2 4 10 12 13 15
This is for BST.