# Construct the binary tree in C++ – you are given two traversal sequences

Once In this tutorial, we will briefly discuss the pre-order and in-order traversal of a binary tree. We then go on to construct the binary tree from the two traversal sequences in C++.

Note:  To construct a tree from traversals, we need at least two of the traversals. With only one traversal sequence we cannot uniquely determine the tree.

### Pre-Order Traversal

In this type of traversal, the route is Root->Left->Right. So we first see the root node, then all the left children and finally the right children.

Morris Preorder Tree Traversal in C++

### In-Order Traversal

In-Order traversal follows the route Left->Root->Right. So we go from left to right, first the left children then it’s the root and finally the right children.

Morris Inorder Tree Traversal in C++

### Illustrative Example

Given a tree:

Pre-order Traversal – 1 2 4 5 6 3

In-Order Traversal – 4 2 5 1 6 3

### Construct Tree from Pre-Order and In-Order Traversals in C++

Data Structures: Maintain a stack and a set

#### Algorithm:

1. Use Pre-Order to find the root of the tree.
2. Once we find the root node, from the elements on the left side of the root node for In-Order traversal, make the left subtree, right side make the right subtree.
3. Next, recursively select each element from the Pre-Order traversal and create left and right subtrees.

#### Example:

In-Order : D B E A F C  Pre-Order : A B D E C F G

Step 1:

Step 2:

#### Code:

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

class Node
{
public:
int val;
Node* left;
Node* right;
Node(int x) { val = x; }
};

set<Node*> s;
stack<Node*> st;

Node* buildTree(int preorder[], int inorder[],int n)
{

Node* root = NULL;
for (int pre = 0, in = 0; pre < n;)
{

Node* node = NULL;
do
{
node = new Node(preorder[pre]);
if (root == NULL)
{
root = node;
}
if (st.size() > 0)
{
if (s.find(st.top()) != s.end())
{
s.erase(st.top());
st.top()->right = node;
st.pop();
}
else
{
st.top()->left = node;
}
}
st.push(node);
} while (preorder[pre++] != inorder[in] && pre < n);

node = NULL;
while (st.size() > 0 && in < n &&
st.top()->val == inorder[in])
{
node = st.top();
st.pop();
in++;
}

if (node != NULL)
{
s.insert(node);
st.push(node);
}
}

return root;
}

void printInorder(Node* node)
{
if (node == NULL)
return;

printInorder(node->left);

cout << node->val << " ";

printInorder(node->right);
}

int main()
{
int in[] = { 4,2,5,1,6,3,7 };

int pre[] = { 1,2,4,5,3,6,7 };

int len = sizeof(in)/sizeof(int);

Node *root = buildTree(pre, in, len);

printInorder(root);
return 0;
}```

Output :

`In Order Traversal : 4,2,5,1,6,3,7`

This was a short tutorial on how to construct a binary tree from two traversal sequences in C++. I hope you find this useful!