Open In App

Convert a Binary Tree to Threaded binary tree | Set 1 (Using Queue)

Last Updated : 10 Feb, 2023
Comments
Improve
Suggest changes
Like Article
Like
Report

We have discussed Threaded Binary Tree. The idea of threaded binary trees is to make inorder traversal faster and do it without stack and without recursion. In a simple threaded binary tree, the NULL right pointers are used to store inorder successor. Wherever a right pointer is NULL, it is used to store inorder successor.

The following diagram shows an example Single Threaded Binary Tree. The dotted lines represent threads. 
 

threadedBT

The following is a structure of a single-threaded binary tree. 

C++
struct Node {
    int key;
    Node *left, *right;

    // Used to indicate whether the right pointer is a normal right
    // pointer or a pointer to inorder successor.
    bool isThreaded;
};
Java Python3 C# JavaScript

How to convert a Given Binary Tree to Threaded Binary Tree? 

We basically need to set NULL right pointers to inorder successor. We first do an inorder traversal of the tree and store it in a queue (we can use a simple array also) so that the inorder successor becomes the next node. We again do an inorder traversal and whenever we find a node whose right is NULL, we take the front item from queue and make it the right of current node. We also set isThreaded to true to indicate that the right pointer is a threaded link. 
Following is the implementation of the above idea.
 

C++
Java Python3 C# JavaScript

Output
Inorder traversal of created threaded tree is
4 2 5 1 6 3 7 

Time complexity: O(n)  

Auxiliary space: O(n) // for queue q

Convert a Binary Tree to Threaded binary tree | Set 2 (Efficient) 


Convert a Binary Tree to Threaded binary tree | Set 1 (Using Queue)
Article Tags :
Practice Tags :

Similar Reads