Hard

# 195. Single Threaded Binary Tree Complete Implementation

In an earlier article "Introduction to Threaded Binary Tree" we have seen what is a threaded binary tree, its types and what advantages it has over normal binary trees.

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 the in-order successor OR all left null pointers will point to the in-order predecessor.

Implementation:

Let's see how the Node structure will look like

```class Node{
Node left;
Node right;
int data;
public Node(int data){
this.data = data;
}
}
```

In normal BST nodes we have left and right references and data but in the threaded binary tree we have a boolean in another field called "rightThreaded". This field will tell whether the node's right pointer is pointing to its in-order successor, but how, we will see it further.

Operations:

We will discuss two primary operations in a single-threaded binary tree

1. Insert node into the tree
2. Print or traverse the tree. ( here we will see the advantage of threaded tree)

Insert():

The insert operation will be quite similar to the Insert operation in the Binary search tree with few modifications.

• To insert a node our first task is to find the place to insert the node.
• Take cur­rent = root.
• start from the cur­rent and com­pare root.data with n.
• Always keep track of the 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 the parent node and make the right pointer point to the parent node and rightThread = true for the 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 the current node, which means the 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 a point to it)  of the 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, with no need for any recursion or any stack for storing the node. Just go to the leftmost node and start traversing the tree using the right pointer and whenever rightThread = false again go to the leftmost node in the right subtree. (See image and code for better understanding)

Output:

```7 20 25 50 99 75 100
```