Be the first user to complete this post

Add to List 
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.
In this article, we will see the complete implementation of a singlethreaded 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 inorder predecessor or successor (left or right) means all right null pointers will point to the inorder successor OR all left null pointers will point to the 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 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 inorder successor, but how, we will see it further.
Operations:
We will discuss two primary operations in a singlethreaded binary tree
 Insert node into the tree
 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 current = root.
 start from the current and compare 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