## 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

- Decide the root node
- Break the given sequence into left sub-tree and right sub-tree
- 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;
}
```

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