# Single 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

Sin­gle Threaded: each node is threaded towards either the in-order pre­de­ces­sor or suc­ces­sor (left or right) means all right null point­ers will point to inorder suc­ces­sor OR 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{
Node left;
Node right;
int data;
public Node(int data){
this.data = data;
}
}
```

In nor­mal BST node we have left and right ref­er­ences and data but in threaded binary tree we have boolean another field called “right­Threaded”. This field will tell whether node’s right pointer is point­ing to its inorder suc­ces­sor, but how, we will see it further.

Oper­a­tions:

We will dis­cuss two pri­mary oper­a­tions in sin­gle threaded binary tree

1. Insert node into tree
2. Print or tra­verse the tree.( here we will see the advan­tage of threaded 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.

• 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 par­ent node while mov­ing left or right.
• if current.data is greater than n that means we go to the left of the root, if after mov­ing to left, the cur­rent = null then we have found the place where we will insert the new node. Add the new node to the left of par­ent node and make the right pointer points to par­ent node and right­Thread = 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 sub­tree, check right­Thread for cur­rent node, means right thread is pro­vided and points to the in order suc­ces­sor, if right­Thread = false then and cur­rent reaches to null, just insert the new node else if right­Thread = true then we need to detach the right pointer (store the ref­er­ence, new node right ref­er­ence will be point to it)  of cur­rent node and make it point to the new node and make the  right ref­er­ence point to stored ref­er­ence. (See image and code for bet­ter understanding)

Tra­verse():

tra­vers­ing the threaded binary tree will be quite easy, no need of any recur­sion or any stack for stor­ing the node. Just go to the left most node and start tra­vers­ing the tree using right pointer and when­ever right­Thread = false again go to the left most node in right sub­tree. (See image and code for bet­ter understanding)

Com­plete Code:

Out­put:

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

#### You may also like...

• eugen_nw

I’m afraid I’ve spot­ted 2 errors in this code, please cor­rect me if I’m wrong.
1. after line #24, the right-threading should be added to newN­ode. Mat­ter of factly, the if on line #23 may never eval­u­ate to true if we do my sug­ges­tion #2.
2. after line #29, cur­rent is no longer right-threaded so the “current.rightThread = false;” assign­ment is missing.