Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

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.

In this arti­cle we will see the com­plete imple­men­ta­tion of sin­gle threaded binary tree.( Click here to read about “dou­ble threaded binary tree”)

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

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 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.
  • 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 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)

Insert Node into Single Threaded Binary Tree

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)

 Traversal in Single Threaded Binary Tree-2 (1)

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.