Table of contents
1.
Introduction 
1.1.
Problem Statement 
1.2.
Explanation of the problem  
1.3.
Sample Example 
2.
Approach - 1 
2.1.
Steps of the Algorithm 
2.2.
Implementation in C++
2.3.
Complexity Analysis 
3.
Approach - 2
3.1.
Steps of the Algorithm 
3.2.
Impementation in C++ 
3.3.
Complexity Analysis 
4.
Frequently Asked Questions 
4.1.
What is a Binary Tree?  
4.2.
List the types of Binary Trees. 
4.3.
Mention a few applications of tree data structures.
5.
Conclusion
Last Updated: Mar 27, 2024

Construct Full Binary Tree using its Preorder traversal and Preorder traversal of its mirror tree

Author Vidhi Singh
0 upvote
Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

Introduction 

A tree is a data structure in Computer Science that deals with representing the data in a non-linear fashion. It is specifically of benefit when the representation requires some kind of hierarchy to be maintained. Additionally, it makes operations like searching, sorting, and finding very efficient. 

The above factors make Trees one of the most important and frequently touched upon topics in technical interviews. 

This article covers one of the famous problems from the topic Trees - Construct Full Binary Tree using its Preorder traversal and Preorder traversal of its mirror tree in detail.  

Problem Statement 

Given the Preorder traversal of a tree and Preorder traversal of its mirror tree, write a function to construct the full binary tree.  

Explanation of the problem  

According to the problem statement, you will be given two sets of sequences -preorder traversal of the tree and preorder traversal of its mirror tree. Using these two sets of sequences, you are to think of a function such that it constructs a full binary tree using these two traversals.   

A full Binary tree is a type of Binary tree with each node with either 0 or 2 child nodes.  

Let us now see the concept of a mirror tree. 

 

Now, preorder traversal of a binary tree is obtained by following a simple rule: visit the root node, then the left subtree, and then the right sub-tree. 

For the above binary tree, the preorder traversal will be: A B D E C F G 

Also, a very important thing to note here is that a binary tree can not be constructed from the given traversals as it does not provide any information regarding which node would occur after or before which. But, since, we are not supposed to construct a binary tree, but specifically a full binary tree, it can be done from the given set of traversals. 

Sample Example 

If the given set of traversals are as follows:

Preorder of the tree={A,B,D,E,C,F,G}
Preorder of the mirror tree={A,C,G,F,B,E,D}  

 

The full binary tree formed is as follows:

 

Approach - 1 

We have preorder traversal of the tree and preorder traversal of its mirror tree. 

Now, we know that in preorder traversal, the first element is the root of the tree. So, according to the example taken above, which is, 

Preorder of the tree={A,B,D,E,C,F,G}
Preorder of the mirror tree={A,C,G,F,B,E,D}   

 

The root is A. The just-next element of the preorder of the tree is the left node. So, B is the left child of the root. The just-next element of the preorder of the mirror tree is the right node. So, C is the right child of the root. Very obviously, B is the root of all nodes in the left sub-tree and C is the root of all nodes in the right sub-tree. All nodes from and B in a preorder traversal of the mirror tree must be in the left sub-tree of root node A and all nodes after C and before B in preorder traversal of the mirror tree must be in the right sub-tree of root node A. Now that, A is the root with B as the left child and C as the right child, elements {B, E, D} are in the left sub-tree, and the elements {C, G, F} are in the right sub-tree.

Now, considering {B, E, D} and {C, G, F} as separate sequences, applying the above procedure until elements are left, the full binary tree can be constructed.  

Refer to the following diagram to make it more clear:

Step 1:

Step 2:

 

Steps of the Algorithm 

  1. Decide the root node 
  2. Break the given sequence into left sub-tree and right sub-tree 
  3. Repeat step 1 and 2 for the subsequnces till all the nodes are not used up

Implementation in C++

#include<bits/stdc++.h>
using namespace std;
 
class Node      //Nodes
{
    public:
        char value;
        Node *left_child,*right_child;
};
 
Node* new_node(int num)     //Creating a new node
{
    Node *t=new Node;
    t->value=num;
    t->left_child=t->right_child=NULL;
    return t;
}
 
void preorder_traversal(Node* root)      //Preorder Traversal of the Full Binary Tree
{
    if(root==NULL)
        return;
 
    cout<<root->value<<" ";
    preorder_traversal(root->left_child);
    preorder_traversal(root->right_child);
}
 
Node* FullBinaryTree(char pre[],char preM[],int &pre_index,int l,int h,int size)     //Constructing full binary tree with given sequences
{   


    if (pre_index>=size||l>h)
        return NULL;
 
    Node* root = new_node(pre[pre_index]);
        ++(pre_index);
 
    if(l==h)
        return root;
     
    int t;
    for(t=l;t<=h;t++)
        if(pre[pre_index]==preM[t])
            break;
 
    if(t<=h)
    {
        root->left_child=FullBinaryTree(pre,preM,pre_index,t,h,size);
        root->right_child=FullBinaryTree(pre,preM,pre_index,l+1,t-1,size);
    }
    return root;   
}
 
int main()
{
	char preorder[]={'A','B','D','E','C','F','G'};
	char preorderMirror[]={'A','C','G','F','B','E','D'}; 
	int size=sizeof(preorder)/sizeof(preorder[0]);
	Node* root=new Node; 
	int pre_index=0;   
	root=FullBinaryTree(preorder,preorderMirror,pre_index,0,size-1,size); 
	cout<<"The preorder traversal of the Full Binary Tree is: ";
	preorder_traversal(root);
        return 0;
}
You can also try this code with Online C++ Compiler
Run Code

 

Output:

The preorder traversal of the Full Binary Tree is: A B D E C F G  

Complexity Analysis 

Time Complexity: O(n) 
Here, ‘n’ is the total nodes in the tree. 

Space Complexity: O(n) 
Here, this space is allocated to the recursion stack.  

Approach - 2

The other way of seeing this problem is that the reverse of the preorder traversal of the mirror tree is the postorder traversal of the original tree. 

If the preorder sequence of the tree and mirrored preorder sequence is as follows:
Preorder of the tree={A,B,D,E,C,F,G}
Preorder of the mirror tree={A,C,G,F,B,E,D}   

Then reverse of the preorder of the mirror tree, which is the postorder traversal of the original tree is: {D, E, B, F, G, C, A} 

So, now our task is to construct the binary tree with preorder and postorder traversal. 

For that, as already mentioned in preorder traversal first element is the root node. So, we have figured out the root node. Now, the second element in the preorder traversal is the left child of the root node. This means that it is the root node for the left subtree. Therefore, all nodes before this left child in the post must be in the left subtree. So, if the above example is considered again, then A is the root node, {D, E, B} is in the left sub-tree, and {F, G, C} is in the right sub-tree. Similarly, it is repeated for both the sub-trees. 

Steps of the Algorithm 

  1. Decide the root node 
  2. Divide the sequence into the left sub-tree and right sub-tree 
  3. Repeat steps 1 and 2 for the subsequnces till all the nodes are not used up 

Impementation in C++ 

#include <bits/stdc++.h>
using namespace std;

class node      //Node of the tree
{
	public:
		char val;
		node *left_child;
		node *right_child;
};

node* new_node(char data)       //Creating new node
{
	node* t=new node();
	t->val=data;
	t->left_child=t->right_child=NULL;
	return t;
}

node* FullBinaryTree(char pre[],char post[],int &pre_index,int l,int h,int size)     //Creating full binary tree
{
	if(pre_index>=size||l>h)
		return NULL;

	node* root=new_node(pre[pre_index] );
	++pre_index;

	if(l==h)
		return root;

	int t;
	for(t=l;t<=h;t++)
		if(pre[pre_index]==post[t])
			break;

	if(t<=h)
	{
		root->left_child=FullBinaryTree(pre,post,pre_index,l,t,size);
		root->right_child=FullBinaryTree(pre,post,pre_index,t+1,h-1, size);
	}

	return root;
}

void reverse(char arr[],int size)  //Reversing the array
{
    for(int i=size-1,j=0;i>size/2;i--,j++)
        arr[j]=arr[i];
}

void preorder(node* root)        //Preorder traversal
{
	if (root==NULL)
		return;
	cout<<root->val<<" ";
	preorder(root->left_child);
	preorder(root->right_child);
}

int main ()
{
	char pre[]={'A','B','D','E','C','F','G'}; 
	char preM[]={'A','C','G','F','B','E','D'}; 
	int size=sizeof(pre)/sizeof(pre[0]); 
	reverse(preM,size);
	int pre_index=0;
	node *root=FullBinaryTree(pre,preM,pre_index,0,size-1,size);

	cout<<"Preorder traversal of Full Binary Tree:";
	preorder(root);
	return 0;
}
You can also try this code with Online C++ Compiler
Run Code

 

Output: 

Preorder traversal of Full Binary Tree: A B D E C F G  

Complexity Analysis 

Time Complexity: O(n) 
Here, ‘n’ is the total nodes in the tree. 

Space Complexity: O(n) 
Space is required for the recursion stack.

Check out this problem - Mirror A Binary Tree

Frequently Asked Questions 

What is a Binary Tree?  

A binary tree is a non-linear data structure that consists of nodes, with each node having a maximum of two children nodes.

List the types of Binary Trees. 

There can be many types of specific binary trees for specific purposes. But, the binary trees are of the following types:

  1. Full Binary Tree
  2. Complete Binary Tree
  3. Perfect Binary Tree
  4. Balanced Binary Tree
  5. Skewed Binary Tree 
  6. AVL Tree 
  7. Binary Search Tree

Mention a few applications of tree data structures.

A few applications of tress include:

  • Operations on hierarchical data.
  • Store data such that searching becomes easy
  • Decrease the time for inserting, deleting, and maintaining sorted data  

Conclusion

This article extensively discusses the programming problem: Construct Full Binary Tree using its Preorder traversal and Preorder traversal of its mirror tree along with their pseudocode, implementation, and time trade-offs

We hope that this blog has helped you enhance your knowledge regarding Construct Full Binary Tree using its Preorder traversal and Preorder traversal of its mirror tree, and if you would like to learn more, check out our articles on Coding Ninjas Blogs

 

Recommended problems -

 

You can refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingJavaScriptSQLSystem Design, and many more!

If you want to test your competency in coding, you may check out the Mock Test Series and participate in the Contests organized on Coding Ninjas Studio! But if you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc; you must look at the Problems, Interview Experiences, and Interview Bundle for placement preparations.

Nevertheless, you may consider our Courses to give your career an edge over others!

Do upvote our blog to help other ninjas grow. 

Happy Coding!

Live masterclass