# Construct a binary tree from InOrder & PostOrder traversals

The binary tree could be constructed as below

• Post-Order traversal is used to find the root of the tree / subtrees in the binary tree. The root node is then used to find its own index in the inorder traversal.
• The last node in the post-order traversal is the root node of the tree.
• In-Order traversal traversal is to find the range of nodes that are in the left sub-tree and the right sub-tree.
• The left sub-tree will have the nodes in the range [ start, index - 1 ]
• The right sub-tree will have the nodes in the range [ index + 1, end ]

Consider the below example in which a binary tree is constructed using the given In-Order and Post-Order traversal. C++ : Program to create a binary tree from a given in-order and post-order tree traversal sequence.

``````#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

class Node {

public:

int val;

Node *left;

Node *right;

Node() : val(0), left(nullptr), right(nullptr) { }

Node(int x) : val(x), left(nullptr), right(nullptr) { }

Node(int x, Node *left_, Node *right_) : val(x), left(left_), right(right_) { }
};

// Recursive function for inorder traversal
void In_Order_Traversal (Node* root) {

if (root != nullptr) {
In_Order_Traversal (root->left);
cout << root->val << ' ';
In_Order_Traversal (root->right);
}
}

// Recursive functioni for postorder traversal
void Post_Order_Traversal (Node* root) {

if (root != nullptr) {
Post_Order_Traversal (root->left);
Post_Order_Traversal (root->right);
cout << root->val << ' ';
}
}

// Recursively construct a binary tree from an in_order and post_order sequence
Node* Construct_Tree (int start, int end, const vector<int>& post_order_seq, int& post_order_index,
unordered_map<int, int>& map_in_order) {

// Nodes exhausted.
if (start > end) {
return nullptr;
}

Node* root = new Node (post_order_seq[post_order_index]);

/* Note : The previous node in the post_order sequence will be the root node
of the right-subtree that would created using the in_order sequence from (start, end) */
post_order_index -= 1;

// Fetch the index of the root node in the in_order sequence to get the range of the left and right subtree nodes.
int index = map_in_order[root->val];

// Recursively construct right sub-tree
root->right = Construct_Tree (index + 1, end, post_order_seq, post_order_index, map_in_order);

// Recursively construct left sub-tree
root->left  = Construct_Tree (start, index - 1, post_order_seq, post_order_index, map_in_order);

return root;
}

// Construct a binary tree from inorder and preorder traversals.
Node* Get_Root (const vector<int>& in_order_seq, const vector<int>& post_order_seq) {

int nodes = post_order_seq.size();

// Use an unordered_map to find the index of a node in the inorder sequence
unordered_map<int, int> map_in_order;
for (int index = 0; index < nodes; index++) {
map_in_order[in_order_seq[index]] = index;
}

int post_order_index = nodes-1;

return Construct_Tree (0, nodes-1, post_order_seq, post_order_index, map_in_order);
}

int main() {

/* Construct the following tree
10
/  \
12   30
/    /  \
44   50   16
*/

vector<int> post_order = { 44, 12, 50, 16, 30, 10 };
vector<int> in_order = { 44, 12, 10, 50, 30, 16 };

cout << "Given post-order traversal : ";
for (const auto& node : post_order) {
cout << node << " ";
} cout << endl;

cout << "Given in-order traversal : ";
for (const auto& node : in_order) {
cout << node << " ";
} cout << endl;

Node* root = Get_Root(in_order, post_order);

cout << "\nPost-order traversal of constructed tree : ";
Post_Order_Traversal(root);

cout << endl;

cout << "In-order traversal of constructed tree : ";
In_Order_Traversal(root);

return 0;
}
``````

Output

``````Given post-order traversal : 44 12 50 16 30 10
Given in-order traversal : 44 12 10 50 30 16

Post-order traversal of constructed tree : 44 12 50 16 30 10
In-order traversal of constructed tree : 44 12 10 50 30 16
``````