Threaded Binary Trees in Data Structure

What is the need for a Threaded Binary Tree?

A Threaded Binary Tree is a specialized form of a binary tree designed to facilitate faster and more efficient in-order traversal without the need for stack or recursion. In a standard binary tree, traversing to the next node requires returning to a common ancestor, which can be computationally expensive. Threaded Binary Trees address this by adding extra "threads" that link nodes directly to their in-order predecessor or successor.

The primary need for a Threaded Binary Tree arises from the desire to optimize traversal processes. Here are some key reasons:

• Space Optimization: Threaded Binary Trees make use of null pointers to store the in-order predecessor and successor, reducing the space complexity that would otherwise be used by stacks in traversal.
• Time Efficiency: By threading the nodes, it eliminates the need to backtrack to ancestors, making in-order traversal faster and more efficient.
• Simplification of Tree Operations: Operations like insertion, deletion, and traversal become more straightforward because the tree inherently maintains a sort of "memory" of the node sequence.
• Non-recursive Traversals: It allows for non-recursive in-order or pre-order traversals, which can be advantageous in environments where stack size is limited or recursion is costly in terms of performance.

Types of Threaded Binary tree

There are two types of Threaded Binary Trees:

1. One-way Threaded Binary Tree
2. Two-way Threaded Binary Tree

1. One-way 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. Two-way 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 it's 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.

Algorithm for Inorder Traversal of Threaded Binary Tree

Here is the in-order traversal of a threaded binary tree:

1. Initialize: Set current to the leftmost node of the tree using the Leftmost(root) function
    
2. Traversal Loop: While current is not null, repeat the following steps
    
3. Process Node: Process the current node by performing the desired action using the ProcessNode function
    
4. Move to In-Order Successor: 
   • If the current node has a right thread: Set current to the node's right thread
      
   • Else: Set current to the leftmost node in the right subtree using Leftmost(current.rightChild)
      
5. Repeat: Go back to step 2 until all nodes are visited
    
6. Finish: The algorithm completes when all nodes in the threaded binary tree are processed
    

Here, the Leftmost function assists in finding the leftmost node in a given subtree, and the ProcessNode function represents any action you want to perform on each visited node during the traversal.

Let us try to implement this algorithm.

• C++
• Java
• Python
• C#
• Javascript

C++

#include <iostream>

class ThreadedBinaryTreeNode {
public:
    int key;
    ThreadedBinaryTreeNode* leftChild;
    ThreadedBinaryTreeNode* rightChild;
    ThreadedBinaryTreeNode* rightThread;

    ThreadedBinaryTreeNode(int value) : key(value), leftChild(nullptr), rightChild(nullptr), rightThread(nullptr) {}
};

// Helper function to find the leftmost node in a subtree
ThreadedBinaryTreeNode* leftmost(ThreadedBinaryTreeNode* node) {
    while (node != nullptr && node->leftChild != nullptr) {
        node = node->leftChild;
    }
    return node;
}

void inOrderTraversalThreadedBinaryTree(ThreadedBinaryTreeNode* root) {
    ThreadedBinaryTreeNode* current = leftmost(root);

    while (current != nullptr) {
        std::cout << current->key << " ";

        if (current->rightThread != nullptr) {
            current = current->rightThread;
        } else {
            current = leftmost(current->rightChild);
        }
    }
}

// Helper function for proper memory cleanup
void deleteTree(ThreadedBinaryTreeNode* root) {
    if (root == nullptr) {
        return;
    }

    deleteTree(root->leftChild);
    deleteTree(root->rightChild);
    delete root;
}

int main() {
    ThreadedBinaryTreeNode* root = new ThreadedBinaryTreeNode(4);
    root->leftChild = new ThreadedBinaryTreeNode(2);
    root->rightChild = new ThreadedBinaryTreeNode(6);
    root->leftChild->leftChild = new ThreadedBinaryTreeNode(1);
    root->leftChild->rightChild = new ThreadedBinaryTreeNode(3);
    root->rightChild->leftChild = new ThreadedBinaryTreeNode(5);
    root->rightChild->rightChild = new ThreadedBinaryTreeNode(7);

    root->leftChild->rightThread = root;
    root->leftChild->leftChild->rightThread = root->leftChild;
    root->rightChild->rightChild->rightThread = nullptr;

    std::cout << "In-Order Traversal:" << std::endl;
    inOrderTraversalThreadedBinaryTree(root);

    // Memory cleanup
    deleteTree(root);

    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Java

public class ThreadedBinaryTreeNode {
    int key;
    ThreadedBinaryTreeNode leftChild;
    ThreadedBinaryTreeNode rightChild;
    ThreadedBinaryTreeNode rightThread;

    public ThreadedBinaryTreeNode(int value) {
        key = value;
        leftChild = null;
        rightChild = null;
        rightThread = null;
    }

    // Helper function to find the leftmost node in a subtree
    private static ThreadedBinaryTreeNode leftmost(ThreadedBinaryTreeNode node) {
        while (node != null && node.leftChild != null) {
            node = node.leftChild;
        }
        return node;
    }

    public static void inOrderTraversalThreadedBinaryTree(ThreadedBinaryTreeNode root) {
        ThreadedBinaryTreeNode current = leftmost(root);

        while (current != null) {
            System.out.print(current.key + " ");

            if (current.rightThread != null) {
                current = current.rightThread;
            } else {
                current = leftmost(current.rightChild);
            }
        }
    }

    // Helper function for proper memory cleanup
    private static void deleteTree(ThreadedBinaryTreeNode root) {
        if (root == null) {
            return;
        }

        deleteTree(root.leftChild);
        deleteTree(root.rightChild);
        root = null;  // Java handles memory cleanup with garbage collection
    }

    public static void main(String[] args) {
        ThreadedBinaryTreeNode root = new ThreadedBinaryTreeNode(4);
        root.leftChild = new ThreadedBinaryTreeNode(2);
        root.rightChild = new ThreadedBinaryTreeNode(6);
        root.leftChild.leftChild = new ThreadedBinaryTreeNode(1);
        root.leftChild.rightChild = new ThreadedBinaryTreeNode(3);
        root.rightChild.leftChild = new ThreadedBinaryTreeNode(5);
        root.rightChild.rightChild = new ThreadedBinaryTreeNode(7);

        root.leftChild.rightThread = root;
        root.leftChild.leftChild.rightThread = root.leftChild;
        root.rightChild.rightChild.rightThread = null;

        System.out.println("In-Order Traversal:");
        inOrderTraversalThreadedBinaryTree(root);

        // Memory cleanup is handled by Java's garbage collector
    }
}

You can also try this code with Online Java Compiler

Run Code

Python

class ThreadedBinaryTreeNode:
    def __init__(self, value):
        self.key = value
        self.leftChild = None
        self.rightChild = None
        self.rightThread = None

def leftmost(node):
    while node and node.leftChild:
        node = node.leftChild
    return node

def in_order_traversal_threaded_binary_tree(root):
    current = leftmost(root)
    while current:
        print(current.key, end=" ")
        if current.rightThread:
            current = current.rightThread
        else:
            current = leftmost(current.rightChild)

def main():
    root = ThreadedBinaryTreeNode(4)
    root.leftChild = ThreadedBinaryTreeNode(2)
    root.rightChild = ThreadedBinaryTreeNode(6)
    root.leftChild.leftChild = ThreadedBinaryTreeNode(1)
    root.leftChild.rightChild = ThreadedBinaryTreeNode(3)
    root.rightChild.leftChild = ThreadedBinaryTreeNode(5)
    root.rightChild.rightChild = ThreadedBinaryTreeNode(7)

    root.leftChild.rightThread = root
    root.leftChild.leftChild.rightThread = root.leftChild
    root.rightChild.rightChild.rightThread = None

    print("In-Order Traversal:")
    in_order_traversal_threaded_binary_tree(root)

if __name__ == "__main__":
    main()

You can also try this code with Online Python Compiler

Run Code

C#

using System;

public class ThreadedBinaryTreeNode
{
    public int Key;
    public ThreadedBinaryTreeNode LeftChild;
    public ThreadedBinaryTreeNode RightChild;
    public ThreadedBinaryTreeNode RightThread;

    public ThreadedBinaryTreeNode(int value)
    {
        Key = value;
        LeftChild = null;
        RightChild = null;
        RightThread = null;
    }

    // Helper function to find the leftmost node in a subtree
    private static ThreadedBinaryTreeNode Leftmost(ThreadedBinaryTreeNode node)
    {
        while (node != null && node.LeftChild != null)
        {
            node = node.LeftChild;
        }
        return node;
    }

    public static void InOrderTraversalThreadedBinaryTree(ThreadedBinaryTreeNode root)
    {
        ThreadedBinaryTreeNode current = Leftmost(root);

        while (current != null)
        {
            Console.Write(current.Key + " ");

            if (current.RightThread != null)
            {
                current = current.RightThread;
            }
            else
            {
                current = Leftmost(current.RightChild);
            }
        }
    }

    public static void Main()
    {
        ThreadedBinaryTreeNode root = new ThreadedBinaryTreeNode(4);
        root.LeftChild = new ThreadedBinaryTreeNode(2);
        root.RightChild = new ThreadedBinaryTreeNode(6);
        root.LeftChild.LeftChild = new ThreadedBinaryTreeNode(1);
        root.LeftChild.RightChild = new ThreadedBinaryTreeNode(3);
        root.RightChild.LeftChild = new ThreadedBinaryTreeNode(5);
        root.RightChild.RightChild = new ThreadedBinaryTreeNode(7);

        root.LeftChild.RightThread = root;
        root.LeftChild.LeftChild.RightThread = root.LeftChild;
        root.RightChild.RightChild.RightThread = null;

        Console.WriteLine("In-Order Traversal:");
        InOrderTraversalThreadedBinaryTree(root);
    }
}

Javascript

class ThreadedBinaryTreeNode {
    constructor(value) {
        this.key = value;
        this.leftChild = null;
        this.rightChild = null;
        this.rightThread = null;
    }
}

function leftmost(node) {
    while (node && node.leftChild) {
        node = node.leftChild;
    }
    return node;
}

function inOrderTraversalThreadedBinaryTree(root) {
    let current = leftmost(root);

    while (current) {
        console.log(current.key, " ");

        if (current.rightThread) {
            current = current.rightThread;
        } else {
            current = leftmost(current.rightChild);
        }
    }
}

// Main function to demonstrate the code
function main() {
    const root = new ThreadedBinaryTreeNode(4);
    root.leftChild = new ThreadedBinaryTreeNode(2);
    root.rightChild = new ThreadedBinaryTreeNode(6);
    root.leftChild.leftChild = new ThreadedBinaryTreeNode(1);
    root.leftChild.rightChild = new ThreadedBinaryTreeNode(3);
    root.rightChild.leftChild = new ThreadedBinaryTreeNode(5);
    root.rightChild.rightChild = new ThreadedBinaryTreeNode(7);

    root.leftChild.rightThread = root;
    root.leftChild.leftChild.rightThread = root.leftChild;
    root.rightChild.rightChild.rightThread = null;

    console.log("In-Order Traversal:");
    inOrderTraversalThreadedBinaryTree(root);
}

// Execute main function
main();

You can also try this code with Online Javascript Compiler

Run Code

Output

4
     / \
    2   6      -> 1, 2, 4, 5
   / \ / \
  1  3 5  7

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

Applications of Threaded Binary Tree

There are some applications of threaded binary trees:

• Efficient In-Order Traversal: Threaded binary trees enhance in-order traversal efficiency by eliminating the need for recursion or stacks
   
• Space Efficiency: Threaded trees save space by eliminating null pointers, reducing memory overhead
   
• Simplified Tree Traversal: Threaded structures simplify and streamline tree traversal algorithms
   
• Fast Searching and Retrieval: Threaded binary trees enable faster navigation, improving the performance of search operations
   
• Threaded Tree-based Iterators: Threaded trees are useful for implementing efficient iterators for various tree traversal orders
   
• Binary Search Tree Operations: Threaded trees enhance efficiency in operations like finding minimum/maximum elements or predecessors/successors

Frequently Asked Questions

What is a threaded binary tree and a normal binary tree?

A threaded binary tree has threads (links) for efficient traversal, while a normal binary tree lacks these threads, requiring recursive methods for in-order traversal.

What is the difference between BST and threaded binary tree?

A Binary Search Tree (BST) follows ordering rules, while a threaded binary tree optimizes in-order traversal by adding threads, reducing recursion and stack usage.

What is the difference between threaded binary tree and AVL tree?

A threaded binary tree uses threads to simplify in-order traversal without recursion or stack, enhancing efficiency. An AVL tree is a self-balancing binary search tree that maintains balance by ensuring height differences between subtrees remain within one, optimizing search and update operations.

Where is threaded binary tree used?

Threaded binary trees are used for efficient in-order traversal, saving space, simplifying tree traversal algorithms, and enhancing operations in scenarios like database indexing.

Conclusion

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. 

Recommended Readings:

• Binary Tree vs Binary Search Tree
• Application of Linked List
• C Programming
• Doubly Linked List