Conversion from a Binary Tree to a Threaded Binary Tree

Introduction

A threaded binary tree is just like a normal binary tree, but they have a specialty in which all the right child pointers that are NULL point to their in-order successor, and all the left child pointers that are NULL point to their in-order predecessor. It helps in facilitating faster tree traversal without requiring a stack or Recursion.

Before moving on, we would first recommend you read about the basics of Understanding Threaded Binary trees.

Structure of Node in Threaded Binary Tree

The structure of a node in a threaded binary tree is quite similar to that of a binary tree but with some modifications. For threaded binary trees, we need to use extra boolean variables in the node structure:

• For the double-threaded binary tree, we need to use two boolean variables: rightThread and leftThread, whereas we only use the rightThread variable for single-threaded binary trees.

• rightThread: This boolean variable is true when the node does not have any right child. In this case, the right pointer will point towards the in-order successor of this node(if it exists), and if it is false, then the right pointer will point towards the right child node.

• leftThread: This boolean variable is true when the node does not have any left child. In this case, the left pointer will point towards the node’s in-order predecessor (if-exists), and if it is false, the left pointer will point towards the left child node.

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

How to convert a binary tree to a threaded binary tree?

Approach 1

In this approach, we do an inorder traversal of the tree and store it using a queue. In this way, the inorder successor will become the next node. Then we do another inorder traversal, and whenever we find a node whose right pointer is NULL, we take the front value from the queue and make it the right of the current node. (Modafinil) The boolean variable named righthread is also set to true to indicate that the right pointer is a threaded link.

But the problem with this approach is that it takes extra space i.e O(n) to keep the inorder traversal and thus requires two traversals. So, now let’s have a look at the more efficient solution.

Approach 2 (Better Solution)

Using this approach, we can convert a binary tree to a threaded binary tree in a single traverse, using no extra space.

• We will do a reverse in-order traversal, which means we will go to the right child first.

• Then in the recursive call, we will pass an additional parameter which is the previously visited node.

• If the right pointer of a node is NULL and the previously visited node is not NULL, we will point the right of the node to the previously visited node and set the boolean rightThread variable to true.

• The previously visited node should not be changed when making a recursive call to the right subtree, and the real previous visited node should be passed when making a recursive call to the left subtree.

#include <bits/stdc++.h>
using namespace std;
 
/* Node Structure in a threaded binary tree */
struct Node{
    int value;
    Node *left, *right;
    bool rightThread;
};
 
// Converts tree to threaded binary tree 
// using given root.
// Function finds rightmost child of root.
Node *convert(Node *root)
{
    // Base cases : Tree is empty or contains a single node
    if (root == NULL)
        return NULL;
    if (root->left == NULL &&
        root->right == NULL)
        return root;
 
    // Find predecessor if it exists
    if (root->left != NULL)
    {
        // Find predecessor of root (Rightmost
        // child of left subtree)
        Node* a = convert(root->left);
 
        // Linking thread from predecessor to root.
        a->right = root;
        a->rightThread = true;
    }
 
    // If current node is rightmost child
    if (root->right == NULL)
        return root;
 
    // Return for right subtree.
    return convert(root->right);
}
 
// Function to return the leftmost node of root.
Node *leftmost(Node *root)
{
    while (root != NULL && root->left != NULL)
        root = root->left;
    return root;
}
 
// Function for inorder traversal of threaded binary tree
void inorder(Node *root)
{
    if (root == NULL) 
    return;
 
    // For finding the leftmost node in normal Binary Tree
    Node *current = leftmost(root);
 
    while (current != NULL)
    {
        cout << current->value << " ";
 
       // If this Node is threaded Node, 
        // then go to inorder successor
        if (current->rightThread)
            current = current->right;
 
       // Or go to the leftmost child in right subtree
        else 
            current = leftmost(current->right);
    }
}
 
// Function to create a new node
Node *newNode(int value)
{
    Node *temp = new Node;
    temp->left = temp->right = NULL;
    temp->value = value;
    return temp;
}
 
int main()
{
    Node* root = newNode(10);
    root->left = newNode(20);
    root->right = newNode(30);
    root->left->left = newNode(40);
    root->left->right = newNode(50);
    root->right->left = newNode(60);
    root->right->right = newNode(70);
 
    convert(root);
 
    cout << "Inorder traversal of created threaded binary tree is \n";
    inorder(root);
    return 0;
}

Output

Inorder traversal of created threaded binary tree is 
40 20 50 10 60 30 70

Time Complexity: O(n)

Space Complexity: O(1) other than function call stack

Frequently Asked Questions

Key Takeaways

This article discussed the two approaches to converting a binary tree to a threaded binary tree. In the first approach, a queue was used to store the values because of which extra space was used, thus requiring two traversals. Whereas in the second approach, no extra space was used, and we achieved our output by traversing just once. Therefore, the second approach is the most efficient solution for converting a binary tree to a threaded binary tree in C++.

By: Mehak Goel