In this problem, we have inorder and preorder of the binary tree. We need to construct a binary tree from the given Inorder and Preorder traversals.
Table of Contents
Example
Input: Inorder= [D, B, E, A, F, C] Preorder= [A, B, D, E, C, F] Output: Pre-order traversal of the tree formed by the given preorder and inorder A B D E C F In-order traversal of the tree formed by the given preorder and inorder D B E A F C Post-order traversal of the tree formed by the given preorder and inorder D E B F C A
Preorder traversal
In preorder traversal, we first print the root node. Then traverse it’s left subtree if present. And finally, traverse it’s right subtree if present.
(The traversal is done in the same way for all nodes)
Inorder traversal
In Inorder traversal, we traverse first the left subtree of the node if present. Then print the root node. And finally, traverse it’s right subtree if present.
(The traversal is done in the same way for all nodes)
- Hence if we have a preorder traversal, then we can always say that the 0th index element will represent root node of the tree.
- And if we have a inorder traversal then for every ith index, all the element in the left of it will be present in it’s left subtree and all the elements in the right of it will be in it’s right subtree.
Using the above two properties, we can construct a tree with the given traversals.
Algorithm for Construct Binary Tree
- Pick the next element in preorder traversal( start picking with index 0 ).
- Create a new node with the data as the picked element.
- Find the picked element’s index from Inorder traversal using hashMaps to reduce time complexity for finding the index.
- Recursively call the same function for elements in the left of the picked element and assign it to the left of the picked node.
- Recursively call the same function for elements in the right of the picked element and assign it to the right of the picked node.
- return root node.
Let’s understand it with an example
Inorder= [D, B, E, A, F, C]
Preorder= [A, B, D, E, C, F]
1: Picked element is A
2: Picked element is B
3: Picked element is D
4: Picked element is E
5: Picked element is C
6: Picked element is F
Implementation
C++ program for Construct Binary Tree
#include<bits/stdc++.h>
using namespace std;
struct node{
char data;
node* left;
node* right;
//constructor
node(char data){
this->data = data;
left = right = NULL;
}
};
//Function to print pre-order of binary tree
void preorder(node* root){
if(root!=NULL){
cout<<root->data<<" ";
preorder(root->left);
preorder(root->right);
}
}
//Function to print in-order of binary tree
void inorder(node* root){
if(root!=NULL){
inorder(root->left);
cout<<root->data<<" ";
inorder(root->right);
}
}
//Function to print post-order of binary tree
void postorder(node* root){
if(root!=NULL){
postorder(root->left);
postorder(root->right);
cout<<root->data<<" ";
}
}
//Function to construct binary tree from it's preorder and inorder traversal
node* buildTree(char in[], char pre[], int start, int end, unordered_map<char, int>& m, int& index){
//base case
if(start>end){
return NULL;
}
char current = pre[index++];
node* p = new node(current);
int inFind = m[current];
p->left = buildTree(in, pre, start, inFind-1, m, index);
p->right = buildTree(in, pre, inFind+1, end, m, index);
return p;
}
int main(){
int n;
cin>>n;
char in[n],pre[n];
for(int i=0;i<n;i++){
cin>>in[i];
}
for(int i=0;i<n;i++){
cin>>pre[i];
}
//make hashmap to find the node in inorder
unordered_map<char,int> m;
for(int i=0;i<n;i++){
m[in[i]] = i;
}
int start = 0,end = n-1, index = 0;
node* root = buildTree(in, pre, start, end, m, index);
cout<<"Pre-order traversal of the tree formed by the given preorder and inorder ";
preorder(root);
cout<<endl;
cout<<"In-order traversal of the tree formed by the given preorder and inorder ";
inorder(root);
cout<<endl;
cout<<"Post-order traversal of the tree formed by the given preorder and inorder ";
postorder(root);
cout<<endl;
}
6 D B E A F C A B D E C F
Pre-order traversal of the tree formed by the given preorder and inorder A B D E C F In-order traversal of the tree formed by the given preorder and inorder D B E A F C Post-order traversal of the tree formed by the given preorder and inorder D E B F C A
JAVA program for Construct Binary Tree
import java.util.*;
public class Main {
public static class node {
char data;
node left;
node right;
//constructor
node(char x) { data = x; }
};
static int index=0;
//Function to construct binary tree from it's preorder and inorder traversal
public static node buildTree(char in[], char pre[], int start, int end, Map<Character, Integer> m)
{
//base case
if(start>end){
return null;
}
char current = pre[index++];
node p = new node(current);
//leaf node
if(start == end){
return p;
}
int inFind = m.get(current);
p.left = buildTree(in, pre, start, inFind-1, m);
p.right = buildTree(in, pre, inFind+1, end, m);
return p;
}
//Function to print pre-order of binary tree
public static void preorder(node root){
if(root!=null){
System.out.print(root.data+" ");
preorder(root.left);
preorder(root.right);
}
}
//Function to print in-order of binary tree
public static void inorder(node root){
if(root!=null){
inorder(root.left);
System.out.print(root.data+" ");
inorder(root.right);
}
}
//Function to print post-order of binary tree
public static void postorder(node root){
if(root!=null){
postorder(root.left);
postorder(root.right);
System.out.print(root.data+" ");
}
}
public static void main(String args[])
{
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
char[] in = new char[n],pre = new char[n];
for(int i=0;i<n;i++){
in[i] = sc.next().charAt(0);
}
for(int i=0;i<n;i++){
pre[i] = sc.next().charAt(0);
}
//make hashmap to find the node in inorder
Map<Character, Integer> m=new HashMap<Character, Integer>();
for(int i=0;i<n;i++){
m.put(in[i], i);
}
int start = 0,end = n-1;
node root = buildTree(in, pre, start, end, m);
System.out.print("Pre-order traversal of the tree formed by the given preorder and inorder ");
preorder(root);
System.out.print("\n");
System.out.print("In-order traversal of the tree formed by the given preorder and inorder ");
inorder(root);
System.out.print("\n");
System.out.print("Post-order traversal of the tree formed by the given preorder and inorder ");
postorder(root);
System.out.print("\n");
}
}
8 D B E A F C G H A B D E C F H G
Pre-order traversal of the tree formed by the given preorder and inorder A B D E C F H G In-order traversal of the tree formed by the given preorder and inorder D B E A F C G H Post-order traversal of the tree formed by the given preorder and inorder D E B F G H C A
Complexity Analysis
Time complexity
We are traversing the given pre-order array only once, hence time complexity will be O(n).
Searching the index of the node in the inorder array will take O(1) time due to hashing.
Space complexity
As we are using an extra space of hashmap(size n), hence the space complexity will also be O(n).