Construct Binary Tree from Given Inorder and Preorder Traversals

Difficulty Level Medium
Frequently asked in Amazon Apple Bloomberg ByteDance Citadel Facebook Google Microsoft Oracle
Binary Tree Depth First Search TreeViews 4717

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.

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)

  1. Hence if we have a preorder traversal, then we can always say that the 0th index element will represent root node of the tree.
  2. 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

  1. Pick the next element in preorder traversal( start picking with index 0 ).
  2. Create a new node with the data as the picked element.
  3. Find the picked element’s index from Inorder traversal using hashMaps to reduce time complexity for finding the index.
  4. Recursively call the same function for elements in the left of the picked element and assign it to the left of the picked node.
  5. Recursively call the same function for elements in the right of the picked element and assign it to the right of the picked node.
  6. 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

Construct Binary Tree from Given Inorder and Preorder Traversals

2: Picked element is B

Construct Binary Tree from Given Inorder and Preorder Traversals

3: Picked element is D

Construct Binary Tree from Given Inorder and Preorder Traversals

4: Picked element is E

Construct Binary Tree from Given Inorder and Preorder Traversals

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).

References

Translate »