A Simple Insertion Approach in Single Threaded Binary Tree

if you have done (or doing) Data Structures , then you definitely got to (or will get to ) familiar with Binary Tree, and shall know (or hear) something about Threaded Binary Tree .

Motive for writing

I was studying Binary Tree Data Structure , then I got to know about Threaded Binary Tree . After going through its theory part, I was curious about its implementation (Basically how insertion takes place in it ?) . 
So, first I googled to see if any easy( to grasp) implementation for insertion operation exists or not. But on googling , I don’t found any implementation which was easy to grasp. 

Then I decided to do it by my own, and After some time, I found an implementation of insertion operation which I think can be easily grasped by anyone.

After that, I decided why not I write an article on it. So that it can reach to large audience.

So here is the article !

Before moving on Insertion 

Before we move on insertion implementation in Threaded Binary Tree . I think it will be good if we discuss a little about Single Threaded Binary Tree.

The idea of Single Threaded Binary Tree is to make

in-order 

traversal faster and do it without using any stack or recursion in Binary Trees. In Single Threaded Binary Tree , a NULL right pointer(of a node) is made to point to

in-order

successor (it it exists).

I am always mentioning its full name (Single Threaded Binary Tree) because a Double Threaded Binary Tree also exist (in this both NULL left and right pointer is made to point to in-order predecessor and in-order successor).

Node Contains : each node (circles in picture) contains 

// c++
// Node structure

struct Node
{
    int key;              // value in node
    Node *left, *right;   // stores left/right child
    bool rightThread;     // stores right Thread for node exists or not
};

Insertion idea !

First , for inserting a new node we will follow the same rule of insertion used in BST . For a node, if new value to insert is smaller than value present in node then new node(with new value) will go in left subtree of node and if new value to insert is larger value than in node , it will go in right subtree of node.

Second , and for making thread ( on which this article mainly focuses ) we will follow following steps : 

1. As we can see from just above picture, that we should have the knowledge of node (in-order successor) with which we are gonna make a thread .

For this , I decided to maintain a variable which stores the node with which we have to make thread.

Node *successor = NULL;

‘ NULL ’ denotes that variable ‘ successor ’ does not contain any value right now.

2. We can also see (from picture), that we need to make a thread, only if a new node is gonna inserted as left child( or left descendent) of any node .

So , At the time of finding position for new node . we will store value in ‘ successor ’ whenever new node will be inserted as left child for a node(already present in tree) .

 // c++
// left subtree
 if (curr->key > el)    // curr is a variable maintaining current node(already present in tree)
                        // with which comparison is taking place
                        // And, el is new key we have to insert
 {
     successor = curr;  // successor only contain value if new node
                        // goes in left subtree of curr node
     curr = curr->left; // go left subtree
 }

3. If new node is going to store as right child ( during finding position for new node) of a node already present in tree , then we will first check if ‘

right Thread

As now , there is no

right Thread

// c++
// right subtree
if (curr->key < el)
 {
     if (curr->rightThread) // if current node has rightThread == true
     {
          curr->right = NULL;         // make right child null of current node
          curr->rightThread = false;  // change value of rightThread for current node from true to false
     }
     curr = curr->right; // go right subtree
 }

4. Finally when we come out of position finding loop (for new node), if successor value does not remains ‘ NULL ‘ (with which we initialize it) . we will store successor value as right child of new node and makes

right Thread

// c++
// adding thread
if (successor) // if successor is not NULL
{
    // newNode stores data of new node 
    newNode->right = successor;     // store successor value in right child of newNode
    newNode->rightThread = true;    // makes rightThread valur of new Node to true
}

This is my idea for insertion in Single Threaded Binary Tree , which I found easy.

Thank you for reading it till the end 🙂 !

And If you are curious to see full implementation of Threaded Binary Tree , you may look at this.

References you may find useful :

1. Binary Search Tree
2. Threaded Binary Tree