# Construct a binary tree from InOrder & PreOrder traversals

The binary tree could be constructed as below

• A given pre-order traversal sequence is used to find the root node of the binary tree to be constructed.
The root node is then used to find its own index in the given inorder traversal sequence. This is needed for constructing the left and the right sub-trees of the root node.
• The first node in the pre-order traversal is the root node of the tree.
• The given in-order traversal sequence is used 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 ]

Note : The order of processing the nodes is from the first to the last node in the given pre-order traversal to construct the root and the sub-trees.

Consider the below example in which a binary tree is constructed using the given In-Order and Pre-Order traversal.

Program to create a binary tree from a given pre-order and in-order tree traversal sequence.

``````from typing import List, Optional # for annotations

# pre_order_index = 0
class Node :

def __init__ (self, val=0, left=None, right=None) :
self.val = val
self.left = left
self.right = right

class Tree :

def __init__ (self, in_order_seq : List[int], pre_order_seq : List[int]) :

self.pre_order = pre_order_seq
self.in_order = in_order_seq
self.nodes = len(pre_order_seq)

# Use a dictionary to find the index of a node in the inorder sequence
self.map_in_order = {}
for index in range(self.nodes) :
self.map_in_order[in_order_seq[index]] = index

# global pre_ordex_index
self.pre_order_index = 0

# Recursively construct a binary tree from an in_order and pre_order sequence
def Construct (self, start : int, end : int) -> Optional[Node] :

# Check if all the nodes in the pre-order sequence are processed. i.e if end < start
if (start > end) :
return None

root = Node (self.pre_order[self.pre_order_index])

# Fetch the index of the root node in the in_order sequence
# to get the range of nodes in the left and right subtrees.
index = self.map_in_order[root.val]

# Process the nodes from left to right
self.pre_order_index += 1

# Recursively construct left sub-tree
root.left = self.Construct (start, index - 1)

# Recursively construct right sub-tree
root.right = self.Construct (index + 1, end)

return root

# Recursive function for inorder traversal
def In_Order_Traversal (root : Node) :

if (root) :
In_Order_Traversal (root.left)
print(root.val, end=' ')
In_Order_Traversal (root.right)

# Recursive function for preorder traversal
def Pre_Order_Traversal (root : Node) :

if (root) :
print(root.val, end=' ')
Pre_Order_Traversal (root.left)
Pre_Order_Traversal (root.right)

# Construct a binary tree from inorder and preorder traversals.
def BuildTree (in_order_seq : List[int], pre_order_seq : List[int]) -> Optional[Node] :

t = Tree (in_order_seq, pre_order_seq)
nodes = len(pre_order_seq)

return t.Construct (0, nodes-1)

def main() :

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

pre_order = [ 10, 12, 44, 30, 50, 16 ]
in_order = [ 44, 12, 10, 50, 30, 16 ]

print("\nGiven in-order traversal : ", end=' ')
for node in in_order :
print(node, end=' ')

print("\nGiven pre-order traversal : ", end=' ')
for node in pre_order :
print(node, end=' ')

root = BuildTree (in_order, pre_order)

print("\nIn-order traversal of the constructed tree : ", end=' ')
In_Order_Traversal(root)

print("\nPre-order traversal of the constructed tree : ", end=' ')
Pre_Order_Traversal(root)

if __name__ == "__main__" :
main()
``````

Output

``````Given in-order traversal :  44 12 10 50 30 16
Given pre-order traversal :  10 12 44 30 50 16
In-order traversal of the constructed tree :  44 12 10 50 30 16
Pre-order traversal of the constructed tree :  10 12 44 30 50 16
``````
``````#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_) { }
};

class Tree {

private:
vector<int> in_order;
vector<int> pre_order;
int pre_order_index;
unordered_map<int, int> map_in_order;

public:
Tree (vector<int> in_order_seq, vector<int> pre_order_seq) {

in_order = in_order_seq;
pre_order = pre_order_seq;
pre_order_index = 0;

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

// Recursively construct a binary tree from an in_order and pre_order sequence
Node* Construct (int start, int end) {

// Check if all the nodes in the pre-order sequence are processed. i.e if end < start
if (start > end) {
return nullptr;
}

Node* root = new Node (pre_order[pre_order_index]);

// Process the nodes from left to right
pre_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 the left sub-tree
root->left  = Construct (start, index - 1);

// Recursively construct the right sub-tree
root->right = Construct (index + 1, end);

return root;
}
};

// 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 preorder traversal
void Pre_Order_Traversal (Node* root) {

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

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

int nodes = pre_order_seq.size();

Tree *t = new Tree(in_order_seq, pre_order_seq);

return t->Construct (0, nodes-1);
}

int main() {

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

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

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

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

Node* root = Build (in_order, pre_order);

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

cout << "\nPre-order traversal of the constructed tree : ";
Pre_Order_Traversal(root);

return 0;
}
``````

Output

``````Given in-order traversal : 44 12 10 50 30 16
Given pre-order traversal : 10 12 44 30 50 16
In-order traversal of the constructed tree : 44 12 10 50 30 16
Pre-order traversal of the constructed tree : 10 12 44 30 50 16
``````
``````import java.util.List;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Arrays;

class Node {

int val;
Node left;
Node right;

Node () { }
Node (int x) { this.val = x; }
Node (int x, Node left_, Node right_) {
val = x;
left = left_;
right = right_;
}
};

class Tree {

List<Integer> in_order;
List<Integer> pre_order;
HashMap<Integer, Integer> map_in_order;
int pre_order_index;

Tree (List<Integer> in_order_seq, List<Integer> pre_order_seq) {

in_order = new ArrayList<Integer>(in_order_seq);
pre_order = new ArrayList<Integer>(pre_order_seq);
map_in_order = new HashMap<Integer, Integer>();
pre_order_index = 0;

// Use an unordered_map to find the index of a node in the inorder sequence
for (int index = 0; index < pre_order_seq.size(); index++) {
map_in_order.put(in_order_seq.get(index), index);
}
}

// Recursively construct a binary tree from an in_order and pre_order sequence
Node Construct (int start, int end) {

// Check if all the nodes in the pre-order sequence are processed. i.e if end < start
if (start > end) {
return null;
}

Node root = new Node (pre_order.get(pre_order_index));

// Process the nodes from left to right
pre_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.get(root.val);

// Recursively construct the left sub-tree
root.left  = Construct (start, index - 1);

// Recursively construct the right sub-tree
root.right = Construct (index + 1, end);

return root;
}

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

if (root != null) {
In_Order_Traversal (root.left);
System.out.print (root.val + " ");
In_Order_Traversal (root.right);
}
}

// Recursive functioni for preorder traversal
void Pre_Order_Traversal (Node root) {

if (root != null) {
System.out.print (root.val + " ");
Pre_Order_Traversal (root.left);
Pre_Order_Traversal (root.right);
}
}

public static void main (String[] args) {

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

List<Integer> pre_order_seq = Arrays.asList (10, 12, 44, 30, 50, 16);
List<Integer> in_order_seq = Arrays.asList (44, 12, 10, 50, 30, 16);

System.out.print ("Given in-order traversal : ");
for (int node : in_order_seq) {
System.out.print(node + " ");
} System.out.println();

System.out.print ("Given pre-order traversal : ");
for (int node : pre_order_seq) {
System.out.print(node + " ");
} System.out.println();

Tree t = new Tree (in_order_seq, pre_order_seq);
Node root = t.Construct (0, pre_order_seq.size() - 1);

System.out.print ("In-order traversal of the constructed tree : ");
t.In_Order_Traversal(root);

System.out.print ("\nPre-order traversal of the constructed tree : ");
t.Pre_Order_Traversal(root);
}
}
``````

Output

``````Given in-order traversal : 44 12 10 50 30 16
Given pre-order traversal : 10 12 44 30 50 16
In-order traversal of the constructed tree : 44 12 10 50 30 16
Pre-order traversal of the constructed tree : 10 12 44 30 50 16
``````