Construct a binary tree from an InOrder & PostOrder traversals
The binary tree could be constructed as below
- A given post-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 last node in the post-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 last to the first node in the given post-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 Post-Order traversal.
Program to create a binary tree from a given in-order and post-order tree traversal sequence.
from typing import List, Optional # for annotations
# post_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], post_order_seq : List[int]) :
self.post_order = post_order_seq
self.in_order = in_order_seq
self.nodes = len(post_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 post_ordex_index
self.post_order_index = self.nodes - 1
# Recursively construct a binary tree from an in_order and post_order sequence
def Construct (self, start : int, end : int) -> Optional[Node] :
# Check if all the nodes in the post-order sequence are processed. i.e if end < start
if (start > end) :
return None
root = Node (self.post_order[self.post_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 right to left
self.post_order_index -= 1
# Recursively construct right sub-tree
root.right = self.Construct (index + 1, end)
# Recursively construct left sub-tree
root.left = self.Construct (start, index - 1)
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 postorder traversal
def Post_Order_Traversal (root : Node) :
if (root) :
Post_Order_Traversal (root.left)
Post_Order_Traversal (root.right)
print(root.val, end=' ')
# Construct a binary tree from inorder and preorder traversals.
def BuildTree (in_order_seq : List[int], post_order_seq : List[int]) -> Optional[Node] :
t = Tree (in_order_seq, post_order_seq)
nodes = len(post_order_seq)
return t.Construct (0, nodes-1)
def main() :
# Construct the following tree
# 10
# / \
# 12 30
# / / \
# 44 50 16
post_order = [ 44, 12, 50, 16, 30, 10 ]
in_order = [ 44, 12, 10, 50, 30, 16 ]
print("\nGiven in-order traversal : ", end=' ')
for node in in_order :
print(node, end=' ')
print("\nGiven post-order traversal : ", end=' ')
for node in post_order :
print(node, end=' ')
root = BuildTree (in_order, post_order)
print("\nIn-order traversal of the constructed tree : ", end=' ')
In_Order_Traversal(root)
print("\nPost-order traversal of the constructed tree : ", end=' ')
Post_Order_Traversal(root)
if __name__ == "__main__" :
main()
Output
Given in-order traversal : 44 12 10 50 30 16
Given post-order traversal : 44 12 50 16 30 10
In-order traversal of the constructed tree : 44 12 10 50 30 16
Post-order traversal of the constructed tree : 44 12 50 16 30 10
#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> post_order;
int post_order_index;
unordered_map<int, int> map_in_order;
public:
Tree (vector<int> in_order_seq, vector<int> post_order_seq) {
in_order = in_order_seq;
post_order = post_order_seq;
post_order_index = post_order_seq.size() - 1;
// Use an unordered_map to find the index of a node in the inorder sequence
for (int index = 0; index < post_order_seq.size(); index++) {
map_in_order[in_order_seq[index]] = index;
}
}
// Recursively construct a binary tree from an in_order and post_order sequence
Node* Construct (int start, int end) {
// Check if all the nodes in the post-order sequence are processed. i.e if end < start
if (start > end) {
return nullptr;
}
Node* root = new Node (post_order[post_order_index]);
// Process the nodes from right to left
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 the right sub-tree
root->right = Construct (index + 1, end);
// Recursively construct the left sub-tree
root->left = Construct (start, index - 1);
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 postorder traversal
void Post_Order_Traversal (Node* root) {
if (root != nullptr) {
Post_Order_Traversal (root->left);
Post_Order_Traversal (root->right);
cout << root->val << ' ';
}
}
// Construct a binary tree from inorder and preorder traversals.
Node* Build (const vector<int>& in_order_seq, const vector<int>& post_order_seq) {
int nodes = post_order_seq.size();
Tree *t = new Tree(in_order_seq, post_order_seq);
return t->Construct (0, nodes-1);
}
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 in-order traversal : ";
for (const auto& node : in_order) {
cout << node << " ";
} cout << endl;
cout << "Given post-order traversal : ";
for (const auto& node : post_order) {
cout << node << " ";
} cout << endl;
Node* root = Build (in_order, post_order);
cout << "In-order traversal of the constructed tree : ";
In_Order_Traversal(root);
cout << "\nPost-order traversal of the constructed tree : ";
Post_Order_Traversal(root);
return 0;
}
Output
Given in-order traversal : 44 12 10 50 30 16
Given post-order traversal : 44 12 50 16 30 10
In-order traversal of the constructed tree : 44 12 10 50 30 16
Post-order traversal of the constructed tree : 44 12 50 16 30 10```
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> post_order;
HashMap<Integer, Integer> map_in_order;
int post_order_index;
Tree (List<Integer> in_order_seq, List<Integer> post_order_seq) {
in_order = new ArrayList<Integer>(in_order_seq);
post_order = new ArrayList<Integer>(post_order_seq);
map_in_order = new HashMap<Integer, Integer>();
post_order_index = post_order_seq.size() - 1;
// Use an unordered_map to find the index of a node in the inorder sequence
for (int index = 0; index < post_order_seq.size(); index++) {
map_in_order.put(in_order_seq.get(index), index);
}
}
// Recursively construct a binary tree from an in_order and post_order sequence
Node Construct (int start, int end) {
// Check if all the nodes in the post-order sequence are processed. i.e if end < start
if (start > end) {
return null;
}
Node root = new Node (post_order.get(post_order_index));
// Process the nodes from right to left
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.get(root.val);
// Recursively construct the right sub-tree
root.right = Construct (index + 1, end);
// Recursively construct the left sub-tree
root.left = Construct (start, index - 1);
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 postorder traversal
void Post_Order_Traversal (Node root) {
if (root != null) {
Post_Order_Traversal (root.left);
Post_Order_Traversal (root.right);
System.out.print (root.val + " ");
}
}
public static void main (String[] args) {
/* Construct the following tree
10
/ \
12 30
/ / \
44 50 16
*/
List<Integer> post_order_seq = Arrays.asList (44, 12, 50, 16, 30, 10);
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 post-order traversal : ");
for (int node : post_order_seq) {
System.out.print(node + " ");
} System.out.println();
Tree t = new Tree (in_order_seq, post_order_seq);
Node root = t.Construct (0, post_order_seq.size() - 1);
System.out.print ("In-order traversal of the constructed tree : ");
t.In_Order_Traversal(root);
System.out.print ("\nPost-order traversal of the constructed tree : ");
t.Post_Order_Traversal(root);
}
}
Output
Given in-order traversal : 44 12 10 50 30 16
Given post-order traversal : 44 12 50 16 30 10
In-order traversal of the constructed tree : 44 12 10 50 30 16
Post-order traversal of the constructed tree : 44 12 50 16 30 10