Single Threaded Binary Tree Complete Implementation

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”)

Single 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

Node Structure of Single threaded binary tree

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

  1. Insert node into 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 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 cur­rent = root .
  • start from the cur­rent and com­pare 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.
  • Insert Node into Single Threaded Binary Tree -1
  • 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)

Insert Node into Single Threaded Binary Tree

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)

 Traversal in Single Threaded Binary Tree-2 (1)

Complete Code:



Output:

7 20 25 50 99 75 100

__________________________________________________
Top Companies Interview Questions..-

Google Microsoft Amazon Facebook more..

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________

  • eugen_nw

    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.

  • lipsa patel

    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

%d bloggers like this: