Threaded Binary Tree

A binary tree is a data structure where every node can have up to two children. There are different ways of traversing through the tree, one of them is in-order traversal. In inorder traversal, you visit the nodes “in order”, which means if the binary tree were a binary search tree, an inorder traversal would give us the elements in an increasing order

However, to perform this traversal, we need to make use of recursion. If not recursion we need to use a stack to mimic the recursion. A Threaded Binary Tree lets us perform inorder traversal without the use of recursion or stack.

Takeaways

Unlike binary trees, threaded binary trees do not require a stack or recursion for their traversal.

What Is a Threaded Binary Tree?

In a threaded binary tree, either of the NULL pointers of leaf nodes is made to point to their successor or predecessor nodes

What is the need for a Threaded Binary Tree?

In a regular tree, the space complexity for insertion/ deletion can range from logarithmic to linear time. We get log time in a balanced binary tree and linear time is the worst case in an unbalanced tree.

In applications where we have a constraint of space, or even when there is a use case of storing large trees in memory, we might need to save up on the extra space invested in the recursion depth. A threaded binary tree is advantageous in such scenarios where space usage is critical

Types of Threaded Binary Trees

Following are Types of Threaded Binary Trees:

Single Threaded

Diagramatic Representation of Single Threaded Binary Tree
As we can see from the diagram, only the right pointer which is NULL point to the successor node in a single-threaded binary tree

Double Threaded

Diagramatic Representation of Double Threaded Binary Tree
In a double threaded Binary tree, the left pointer also points to its predecessor node

Node Structure in a Threaded Binary Tree

// single threaded

struct Node{
   int data ;
   Node *left ;
   Node *right ;
   bool rightThread ;
}

// double threaded

struct Node{
   int data ;
   Node *left ;
   Node *right ;
   bool leftThread ;
   bool rightThread ;
}

What Is the Significance of a Bool Variable in a Structure?

Consider a single threaded binary tree. Any node in the binary tree can have its right pointer either to a child or the next successor node (which might not be the child node).

Hence we need a boolean variable that tells us whether the right pointer is pointing to a child or the next successor node

Inorder Traversal Using Threads

Let us see how inorder traversal actually works in a single threaded binary tree now

The following steps take place in the diagram above:

1. We go to the left most node 1
2. Node 1 has boolean rightThread as true, hence next we visit its inOrder successor node 2
3. Node 2 has a right child, so we visit Node 3 next
4. Node 3 does not have a right child, ie the rightThread boolean is true, so we visit Node 4 next
5. Node 4 has a right child so we visit Node 5 and finish traversal

We will write a function which will give us the inOrder successor of a node:

struct Node* findSuccesor(Node* node) {
if(node -> rightTread == true){ 
    return node --> right; //straightaway return the parent node if present
}
if(root -> right != NULL){
    while(root -> left != NULL) { //if left child is present return the leftmost node
        root = root -> left;
    }
    return root;
}
return NULL; //if no children are present then this is the last node

The following code prints the node inOrder:

void printInOrder() {

    while(root -> left != NULL){
        root = root -> left;

    while(root != NULL){
        print(root->val);
        root = findSuccesor(root);
    }
}

The Operations in a Threaded Binary Tree

Let us now discuss how to insert/ search/ delete in a double threaded binary tree. We will be considering a binary search tree while discussing these example

1. Insert

To insert a key, we first need to find the to-be parent of the new key. In order to find the parent, we need to follow these steps:

1. If the node we wish to insert is greater than the current node, then we need to move right
2. If the node we wish to insert is lesser than the current node, then we need to move left
3. In a usual BST, we might encounter a node that has its left or right child NULL, however, this is not possible in a double threaded BST. In such cases, we have to break out of the loop of these 3 steps, as that node will be the parent

Code:

void insert(Node* root, int key) {

    Node* curr = root;
    Node* parent = NULL; //to keep track of the to-be parent

    while(curr != NULL) {

        if(curr->val == key){
            print("Node is already present in the tree");
            break;
        }

        parent = curr;

        if(key > curr->val){
            if(curr->rightThread == false)
                curr = curr->right;
            else //means there is no right child of curr
                break;
        }
        else{
            if(curr->leftThread == true)
                curr = curr->left;
            else
                break;
        }
    }

    Node* newNode = new Node;
    newNode->val = key;
    newNode->leftThread = true;
    newNode->rightThread = false;

    if(parent == NULL){
        root = temp;
        root->left = NULL;
        root->right = NULL;
    }
    else if(key < parent.val){
        newNode->left = parent->left;
        newNode->right = parent;
        newNode->leftThread = false;
        parent->left = newNode;
    }
    else{
        newNode->right = parent->right;
        newNode->left = parent;
        newNode->rightThread = false;
        parent->right = newNode;
    }
}

2. Search

Searching a node in a double threaded binary tree is very easy due to its structure. We traverse through as follows:

1. If the key we are searching for is lesser than the value of the currentNode, we move left
2. If the key is greater than the value of the current node, we move right

Code:

Node* search(Node* root, int key){
    Node* curr = root;

    while(curr != NULL){
        if(curr.val == key){
            return curr;
        }
        if(key < curr.val){
            curr = curr->left;
        }
        else{
            curr = curr->right;
        }
    }
    return NULL;
}

3. Delete

Deletion of a node involves a lot of cases, hence we will discuss the approach and write the pseudo code only. In all these cases, it is assumed that you have searched for the node to be deleted in the BST

Case 1: Deleting a leaf node

If the leaf node to be deleted is the left child of a parent node, we need to update the predecessor node of the parent node.

if(nodeToBeDeleted->rightThread == true){
    parentNode = nodeToBeDeleted->right;
    parentNode->left = nodeToBeDeleted->left;

}

If the leaf node to be deleted is the right child of a parent node, we need to update the successor node of the parent node.

if(nodeToBeDeleted->leftThread == true){
    parentNode = nodeToBeDeleted->left;
    parentNode->right = nodeToBeDeleted->right;
}

Case 2: Deleting a node that has one child

If the node that is to be deleted has a left child, the inOrder successor of the child node has to be updated

If the node that is to be deleted has a right child, the inOrder predecessor of the child node has to be updated

Case 3: Deleting a node that has two children

In such a case, we need to replace the node to be deleted with its inOrder successor:

1. The inOrder successor of the node to be deleted is found out
2. Then we find the leftmost child of the successor node, which is a replacement for the node to be deleted
3. We copy the information of the leftmost child in the node to be deleted, and then delete the leftmost child using either case 1 or case 2

Time and Space Complexity of Operations

The time complexity for insertion, deletion, and searching in a threaded binary tree is the same as that of a BST, as we need to perform operations maximum up to the depth of the tree. The depth of a threaded BST is also log(n) where n is the total number of nodes in the tree

Hence all operations take up O(log(n)) time complexity

However, since we do not use any extra space for any of the operations, the auxilliary space complexity is O(1)

Conclusion

1. A threaded binary tree is a tree that maintains the predecessor and successor node of every node in the tree
2. If the right child of a node is NULL, the right pointer of that node points to the inOrder successor of the node
3. If the left child of a node is NULL, the left pointer of that node points to the inOrder predecessor of the node
4. Accordingly, if a tree maintains just the right successor information with its nodes, it is a single threaded binary tree
5. If the tree maintains both the successor and predecessor information, it is a double threaded binary tree
6. In the node structure, we maintain a boolean field that tells whether the left or right pointer is pointing to a child node or a parent node
7. A threaded binary tree lets us perform traversal, insertion, deletion and search operations without using any extra space
8. The time complexity of these operations however remains O(log(n))