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 single threaded binary tree.( Click here to read about “double threaded binary tree”)

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

**Single Threaded**: each node is threaded towards either the in-order predecessor or successor (left **or** right) means all right null pointers will point to inorder successor **OR** all left null pointers will point to inorder predecessor.

**Implementation:**

Let’s see how the Node structure will look like

class Node{ Node left; Node right; int data; boolean rightThread; public Node(int data){ this.data = data; rightThread = false; } }

In normal BST node we have left and right references and data but in threaded binary tree we have boolean another field called “rightThreaded”. This field will tell whether node’s right pointer is pointing to its inorder successor, but how, we will see it further.

**Operations**:

We will discuss two primary operations in single threaded binary tree

- Insert node into tree
- Print or traverse the tree.( here we will see the advantage of threaded 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.
- Take current = root .
- start from the current and compare root.data with n.
- Always keep track of parent node while moving left or right.
- if current.data is greater than n that means we go to the left of the root, if after moving to left, the current = null then we have found the place where we will insert the new node. Add the new node to the left of parent node and make the right pointer points to parent node and rightThread = true for new node.
- if current.data is smaller than n that means we need to go to the right of the root, while going into the right subtree, check rightThread for current node, means right thread is provided and points to the in order successor, if rightThread = false then and current reaches to null, just insert the new node else if rightThread = true then we need to detach the right pointer (store the reference, new node right reference will be point to it) of current node and make it point to the new node and make the right reference point to stored reference. (See image and code for better understanding)

**Traverse():**

traversing the threaded binary tree will be quite easy, no need of any recursion or any stack for storing the node. Just go to the left most node and start traversing the tree using right pointer and whenever rightThread = false again go to the left most node in right subtree. (See image and code for better 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 SingleThreadedBinaryTree { | |

public static Node root; | |

public void insert(Node root, int id){ | |

Node newNode = new Node(id); | |

Node current = root; | |

Node parent = null; | |

while(true){ | |

parent = current; | |

if(id<current.data){ | |

current = current.left; | |

if(current==null){ | |

parent.left = newNode; | |

newNode.right = parent; | |

newNode.rightThread = true; | |

return; | |

} | |

}else{ | |

if(current.rightThread==false){ | |

current = current.right; | |

if(current==null){ | |

parent.right = newNode; | |

return; | |

} | |

}else{ | |

Node temp = current.right; | |

current.right = newNode; | |

newNode.right = temp; | |

newNode.rightThread=true; | |

return; | |

} | |

} | |

} | |

} | |

public void print(Node root){ | |

//first go to most left node | |

Node current = leftMostNode(root); | |

//now travel using right pointers | |

while(current!=null){ | |

System.out.print(" " + current.data); | |

//check if node has a right thread | |

if(current.rightThread) | |

current = current.right; | |

else // else go to left most node in the right subtree | |

current = leftMostNode(current.right); | |

} | |

System.out.println(); | |

} | |

public Node leftMostNode(Node node){ | |

if(node==null){ | |

return null; | |

}else{ | |

while(node.left!=null){ | |

node = node.left; | |

} | |

return node; | |

} | |

} | |

public static void main(String[] args) { | |

root = new Node(100); | |

SingleThreadedBinaryTree st=new SingleThreadedBinaryTree(); | |

st.insert(root,50); | |

st.insert(root,25); | |

st.insert(root,7); | |

st.insert(root,20); | |

st.insert(root,75); | |

st.insert(root,99); | |

st.print(root); | |

} | |

} | |

class Node{ | |

Node left; | |

Node right; | |

int data; | |

boolean rightThread; | |

public Node(int data){ | |

this.data = data; | |

rightThread = false; | |

} | |

} |

**Output:**

7 20 25 50 99 75 100

I’m afraid I’ve spotted 2 errors in this code, please correct me if I’m wrong.

1. after line #24, the right-threading should be added to newNode. Matter of factly, the if on line #23 may never evaluate to true if we do my suggestion #2.

2. after line #29, current is no longer right-threaded so the “current.rightThread = false;” assignment is missing.

One mistake is in insert method else condition we need current.rightThread = false;

And the correct output should be 7 20 25 50 75 99 100