Understanding Threaded Binary Trees

1. Introduction

In this tutorial, we’ll dive into a very interesting subbranch of the binary tree, the threaded binary trees.

2. Binary Trees and Threaded Binary Trees

A binary tree is a data structure in which each node stores data and has at most two children, the left and right child. A node that does not have the left or right child is termed a leaf node.

Leaf nodes have null values for their left and right children.

Threaded binary trees differ from binary trees mainly in one aspect. The leaf’s null (empty) left and child pointers are replaced with threads that point the nodes to their in-order successor or predecessor. Here’s an example of a threaded binary tree with threads pointing to the in-order successor:

Threaded Binary Tree

This modification’s primary benefit is that it simplifies the inorder traversal of trees without recursion or any auxiliary data structure such as stacks.

3. Node Representation and Types of Threaded Binary Trees

The threads in the threaded binary trees represent the pointers to the inorder successor node and the inorder predecessor nodes of the tree (if they exist). We can define two types of threaded binary trees based on this definition.

Single Threaded Binary Tree: The NULL right pointer points to the in-order successor node of the tree
Double Threaded Binary Tree: The left and right NULL pointers point to the in-order predecessor and successor node respectively

The double-threaded binary tree gives an edge over the single-threaded version by providing easy and fast access to the in-order predecessor. This speeds up postorder or reverse inorder tree traversals.

A Node of this threaded binary tree can be represented as follows:

ThreadedNode {
    int data;
    ThreadedNode left;
    ThreadedNode right;
    bool isLeftThread;
    bool isRightThread;
}

The node structure of a threaded binary tree, while majorly similar to the binary tree differs in the two new boolean attributes. The isLeftThread and isRightThread attributes denote if the left and right pointers point to the predecessor and successor or not.

4. Tree Traversals of a Threaded Binary Tree

Traversing through the nodes of the tree helps us solve problems using the tree data structure. The Depth First Search approach allows us to visit the nodes of the tree in 3 fashions, inorder, preorder, and postorder.

As this is a depth-first approach, it involves visiting the left and right children in some order.

4.1. Inorder Traversal

The inorder traversal of a binary tree involves visiting the left sub-tree, followed by visiting the root node, and finally the right sub-tree.

Inorder traversal of a Threaded binary tree is easier owing to its threading mechanism. Let’s look at the algorithm to print the nodes of a threaded binary tree using the inorder traversal:

algorithm inorderTraversal(tree):
    // INPUT 
    // tree = a threaded binary tree root
    // OUTPUT
    // the function prints the tree's node values in depth-first inorder

    current = tree
    while current is not NULL and current.isLeftThread is false:
        current = current.left
    
    while current != NULL:
        print(current.data)
        
        // Find the inorder successor
        if current.isRightThread == true:
            current = current.right
        else:
            current = current.right
            // Find the leftmost node in the right subtree
            while current != NULL and current.isLeftThread == false:
                current = current.left

We start the inorder traversal by first moving to the leftmost node of the threaded binary tree. This is easily achieved by visiting the left node of the current node until the current node is NULL and isLeftThread is false.

We print the node value when we have reached the leftmost node.

The next step involves finding the next inorder successor of the tree. The right thread pointer points to the in-order successor of a threaded binary tree. If there is no such node, we move the current node to the right subtree and find the leftmost node in the right subtree.

We repeat the above steps until the whole tree is visited.

Let’s take an example:

The Double Threaded binary tree representation of the above tree is:

The inorder traversal of this tree is: 1, 2, 3, 4, 5

4.2. Preorder Traversal of a Threaded Binary Tree

Preorder traversal is a depth-first traversal technique where we start by visiting the root node and then we move to the left and the right subtrees.

If the left child does not exist, we leverage the threads of the threaded binary tree and move to the right thread to visit the next node. We repeat the above steps until we visit all the nodes of the tree:

algorithm preorderTraversal(tree):
    // INPUT 
    // tree = a threaded binary tree root
    // OUTPUT
    // the function prints the tree's node values in depth-first preorder
    
    current = tree
    
    while current != NULL:
        
        print(current.data)
        
        if current.left != NULL:
            current = current.left
        else:
            while current != NULL and current.isRightThread == true:
                current = current.right
            if current != NULL:
                current = current.right

The preorder representation of the same threaded binary tree is: 4, 2, 1, 3, 5

4.3. Postorder Traversal of a Threaded Binary Tree

In the postorder traversal of a threaded binary tree, we visit the left and right subtrees before visiting the root node. The threaded nature of the threaded binary tree poses some challenges.

Every tree node points to its in-order successor with the threads, and visiting the right subtree before the root node is difficult. Therefore, some additional data structure is essential to perform the intended postorder traversal.

A stack data structure is used in this case to keep track of all the nodes while moving to the leftmost node:

We start at the leftmost node and move to the node with no left child
We keep pushing the nodes in the path to the stack
Once we have reached the node, we take nodes from the stack and handle the right threads appropriately

This way, we visit the nodes in left-right-root order.

Here’s the algorithm in pseudo-code:

algorithm postorderTraversal(tree):
    // INPUT 
    // tree = a threaded binary tree root
    // OUTPUT
    // the function prints the tree's node values in depth-first postorder    
    stack = empty stack
    current = tree
    lastVisited = NULL
    
    while not stack.isEmpty() or current != NULL:
        if current != NULL:
            stack.push(current)
            current = current.left if current.left != NULL else current.right
        else:
            nextNode = stack.peek()
            if peekNode.right != NULL and lastVisited != nextNode.right:
                current = nextNode.right
            else:
                print(nextNode.data)
                lastVisited = stack.pop()

The postorder traversal of the threaded binary tree is: 1, 3, 2, 5, 4

5. Insertion of a Node in a Threaded Binary Tree

Inserting a new node in a threaded binary tree can be broken down into a couple of steps.

5.1. Steps to Insert

The first step involves searching for the insertion position.

We start the search from the root node and repeat the following steps. If the new node’s key is:

smaller than the current node, we move to the left child
greater, we move to the right child.
If we encounter a NULL left or right child, we have found the insertion position

We then create the node and modify the left and right threads accordingly:

If the new node is inserted as the left child:
- we set the left child of the new node to point to the left child of the current node
- and then we set the right child of the new node to point to the current node, essentially making it the in-order successor
If the new node is inserted as the right child:
- we set the right child of the new node to point to the right child of the current node
- and then we set the left child of the new node to point to the current node (in-order predecessor)

Finally, we complete the insertion by updating the threads of the parent node as well.

5.2. Pseudocode for Inserting a Node

The algorithm is formally shown here:

algorithm InsertInThreadedBinaryTree(root, nodeToInsert)
    // INPUT 
    // root = root node of a threaded binary tree,
    // nodeToInsert = new node to be inserted in binary tree

    // OUTPUT
    // root of the new threaded binary tree

    if root is NULL
        root = nodeToInsert
        nodeToInsert.left = NULL
        nodeToInsert.right = NULL
        return root
    
    current = root
    parent = NULL
    
    # Searching for the correct position to insert the new node
    while current != NULL
        parent = current
        
        if nodeToInsert.key < current.key
            if current.left == NULL  # Break when position is found
                break
            current = current.left
        else
            if current.right == NULL  # Break when position is found
                break
            current = current.right
    
    # Insert as the left child
    if nodeToInsert.key < parent.key
        nodeToInsert.left = parent.left
        nodeToInsert.right = parent
        parent.left = nodeToInsert
        
        # If left thread exists, update it to point to the new node
        if nodeToInsert.left != NULL
            parent.isLeftThread = False
            nodeToInsert.isLeftThread = True
    
    # Insert as the right child
    else
        nodeToInsert.right = parent.right
        nodeToInsert.left = parent
        parent.right = nodeToInsert
        
        # If right thread exists, update it to point to the new node
        if nodeToInsert.right != NULL
            parent.isRightThread = False
            nodeToInsert.isRightThread = True
    
    return root

6. Advantages and Disadvantages of a Threaded Binary Tree

A threaded binary tree has several advantages over the traditional binary tree because of its threaded nature. It eases the traversals of trees and makes it more efficient. Therefore, a threaded binary tree is the optimum choice for a scenario where the tree is seldom modified but traversed frequently.

However, there is an added complexity that comes with the threaded nature, especially the change in algorithms that is required to insert or delete a node or traverse a threaded binary tree. As a threaded binary tree holds more information, additional space is also required.

7. Conclusion

In this article, we looked into what a threaded binary tree is and explored the different operations that can be performed in a binary threaded tree. Finally, we understood the importance of a threaded binary tree and how it benefits different tree traversals by maintaining additional information in its null pointers.

Persistence

REST

Security