Understanding Threaded Binary Trees

Introduction 

We know every node of the binary tree stores the data value of the node and the address pointers of the left and right children. If a node in a binary tree does not have a left or right child or is a leaf node, then the child node’s absence is represented by a null pointer.

Consider the following Binary Tree.

Many nodes present in this tree hold a NULL value in their left or right child pointer (Denoted by sketched fields). The space occupied by these null values can be used to store some kind of valuable information.

One possible way to utilise this space is to have a special pointer that points to nodes higher in the tree (i.e. ancestors). These special pointers are called threads, and the binary tree having such pointers is called a threaded binary tree. 

A Threaded Binary Tree is a variant of a normal Binary Tree that facilitates faster tree traversal and does not require a Stack or Recursion. It decreases the memory wastage by setting the null pointers of a leaf node to the in-order predecessor or in-order successor.

What is a Threaded Binary tree? 

In a Threaded Binary Tree, the nodes will store the in-order predecessor/successor instead of storing NULL in the left/right child pointers.

So the basic idea of a threaded binary tree is that for the nodes whose right pointer is null, we store the in-order successor of the node (if-exists), and for the nodes whose left pointer is null, we store the in-order predecessor of the node(if-exists).

One thing to note is that the leftmost and the rightmost child pointer of a tree always points to null as their in-order predecessor and successor do not exist. 

To understand this, let’s look at an example of a Threaded Binary Tree.

In the above-given figure, the right pointer of node value 6 points to 9. 

• Now, we will check the left pointer of node 9, and if it is NULL, then we modify the reference to the predecessor of the node, which is 6.
• Then, we will check for the right pointer, and if it is also NULL, we will point it to the successor node, which is 10. Thus, it will point to 10.
• We point to in-order predecessors/successors in left/right pointers using threads (denoted by dotted lines) as shown in the figure above, and that is why it is known as a Threaded Binary Tree. 
• Since the leftmost pointer of this tree is the left pointer of node value 5 and the rightmost pointer of this tree is the right pointer of node value 20, they both point to NULL.

The main idea behind setting such a structure is to make the inorder and preorder traversal of a binary tree faster without using any additional data structure (e.g. auxiliary stack) or memory for its traversal.

Types of Threaded Binary tree

There are two types of Threaded Binary Trees:

1. Single-Threaded Binary Tree 

In this type, if a node has a right null pointer, then this right pointer is threaded towards the in-order successor’s node if it exists. 

Node Structure of Single-Threaded Binary Trees: The structure of a node in a binary threaded tree is quite similar to that of a binary tree, but with some modifications. In threaded binary trees, we need to use extra boolean variables in the node structure. For single-threaded binary trees, we use only the rightThread variable.

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

The following diagram depicts an example of a Single-Threaded Binary Tree. Dotted lines represent threads.

In the figure given above, you can observe the node value 20 does not have any child nodes. So, the right pointer of node value 20 is null and therefore, it is pointing to its in-order successor (node value 30) through a thread. Similarly, the other nodes of this tree containing a right null pointer refer to their in-order successor, as shown.

2. Double-Threaded Binary Tree

In this type, the left null pointer of a node is made to point towards the in-order predecessor node and the right null pointer is made to point towards the in-order successor node. 

Node Structure of Double-Threaded Binary Trees: For the double-threaded binary tree, we use two boolean variables: rightThread and leftThread.

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

Here, the leftThread and rightThread boolean variables help us to differentiate whether the left/right pointer stores the in-order predecessor/successor or left child/right child.

Let’s look at an example to understand this. 

This is how a Double-Threaded Binary Tree looks like. You can observe here that node value 40 have no left and right child. So, its left pointer points to its in-order predecessor (node value 30) and its right pointer points towards its in-order successor (node value 50). Similarly, the other nodes of this tree with a left/right null pointer refers to their in-order predecessor/successor using threads. 

To look at the implementation of these trees, refer to our upcoming blogs on it.

Advantages of Threaded Binary Tree

Let’s discuss some advantages of a Threaded Binary tree.

• No need for stacks or recursion: Unlike binary trees, threaded binary trees do not require a stack or recursion for their traversal. 
• Optimal memory usage: Another advantage of threaded binary tree data structure is that it decreases memory wastage. In normal binary trees, whenever a node’s left/right pointer is NULL, memory is wasted. But with threaded binary trees, we are overcoming this problem by storing its inorder predecessor/successor.
• Time complexity: In-order traversal in a threaded binary tree is fast because we get the next node in O(1) time than a normal binary tree that takes O(Height). But insertion and deletion operations take more time for the threaded binary tree.
• Backward traversal: In a double-threaded binary tree, we can even do a backward traversal.

Disadvantages of Threaded Binary tree

Let’s discuss some disadvantages that might create a problem for a programmer using this.

• Complicated insertion and deletion: By storing the inorder predecessor/ successor for the node with a null left/right pointer, we make the insertion and deletion of a node more time-consuming and a highly complex process.
• Extra memory usage: We use additional memory in the form of rightThread and leftThread variables to distinguish between a thread from an ordinary link. (However, there are more efficient methods to differentiate between a thread and an ordinary link).

Frequently Asked Questions

Key Takeaways

Often, while using a binary tree, we come across nodes that have less than two children. The linked list representation of these trees stores NULL for a node’s left/right pointers in such scenarios. To avoid this memory wastage, we introduce the concept of Threaded Binary Trees.

A binary tree is threaded by making all left child pointers that would normally be a null point to its inorder predecessor of the node  (if it exists) and all right child pointers that would normally be a null point to its inorder successor of the node (if it exists).

It is of two types- Single-Threaded Binary Tree and Double-Threaded Binary Tree. We have also discussed its advantages and disadvantages. 

By Mehak Goel