Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
2.1.
Example
3.
Approach
3.1.
Algorithm
3.2.
Implementation in C++
3.3.
Implementation in Java
3.4.
Complexity Analysis
4.
Frequently Asked Questions
4.1.
What is a binary tree?
4.2.
What is preorder traversal?
4.3.
What is inorder traversal?
4.4.
What is a root node?
4.5.
Can a binary tree have a zero node as a children node?
5.
Conclusion
Last Updated: Mar 27, 2024
Hard

Check if given inorder and preorder traversals are valid for any Binary Tree without building the tree

Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction

Solving problems based on a particular topic repeatedly until you have completely understood all the aspects of the topic is an excellent way of learning. There are multiple problems based on the Binary tree that can help you completely understand its properties.

introduction image

This blog will discuss one frequently asked question based on binary trees in coding interviews. The problem we will discuss is a variation of the problem known as Construct a Binary Tree from a given Preorder and Inorder traversal, and we will also discuss the working of this problem, and then we will focus on our current problem.

Problem Statement

We will be given the two arrays or vectors, let's assume arrays for now, ‘array1’, and ‘array2’, of size ‘N’, in which ‘array1’ contains the preorder traversal of a tree, and ‘array2’ has the inorder traversal of a tree. Our task is to find if we can construct a binary tree using a preoder and an inorder array.

In a tree, if a parent node has at most 2 children, then the tree is known as a binary tree. When validating the given arrays, we must keep this binary tree property in mind.

As we have mentioned earlier, the problem we are currently discussing is a variation of another problem. In the main problem, our task is to construct a binary tree using the preoder and inorder traversals given to us in the form of an array. But here, our goal is to check whether the given preorder and inorder array are valid for any binary tree without actually constructing a tree. In short, we cannot create a binary tree with given inputs; we must look for another way.

But it is best to discuss the working of the main problem because it will give us the logic to implement the solution for our current problem. The logic we will use in our current problem is similar to the logic of the main problem. We need to add some conditions to the current problem.

Example

You can use an array or vector to store the inorder and preorder tree traversal.

Input: Inorder Array and Preorder Array are given as input,

Preorder[] = [10,20,40,50,30]

Inorder[] = [40,20,50,10,30]
 

dry run image

 

dry run image

In the case of Inorder traversal, we traverse the tree following this pattern:

  • Left
  • Root
  • Right
     

In the case of Preorder traversal, we traverse the tree following this pattern:

  • Root
  • Left
  • Right
     

If the Preorder traversal of the tree is given, the first element in the traversal will always be the root. So in our example, where the preorder array is,

Preorder[] = [10,20,40,50,30],

The root is 10. 

But with the help of only preorder traversal alone, we need help understanding which elements lie in the root's left and right subtree. So we need to make use of the inorder array. 

Inorder[] = [40,20,50,10,30]

Element 10 lies in the third index of the inorder array. So therefore, everything to the left of 10 (i.e., from index 0 to 2) should lie in the left subtree of 10. Similarly, everything to the right of 10 in the array (i.e., index 4) should lie in the right subtree.

dry run image

But how will we know the root of the left and right subtrees? We have to look at the next element in the preorder traversal array. The next element in the preorder traversal array is the root of the left subtree (if the left subtree exists).

The next element in the preorder traversal array is 20.

Preorder[] = [10,20,40,50,30].

Therefore the root of the left subtree is 20.

dry run image

Now to know what comes in the left and right subtree of 20, we again take the help of an inorder traversal array. 

Inorder[] = [40,20,50,10,30]

20 lies in index 1 and elements to the left of it lie in the left subtree, and the element to its right lies in the right subtree. So 40 should be the left child, and 50 should be the right child of 20.

dry run image

Now that we are done with the entire left subtree let’s build the right subtree. As element 30 is the only node left, it connects to root 10.

Our final constructed binary tree is:

dry run image

While building the tree, we can notice a recursive pattern in the above steps, and we can then follow all the steps to construct the tree. 

We are doing a preorder traversal of the tree and building the tree with the help of the inorder array.

You can check out the Construct a Binary Tree from a given Preorder and Inorder traversal blog for implementation of the above approach.

Now that we have understood the problem statement let's talk about how to solve this problem.

Also Read About, Binary Tree Postorder Traversal.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Approach

Now that you have understood the logic of the above example. In that case, it will be fine for you to understand the approach we will use to check whether the given preorder and inorder array are valid for a binary tree without constructing it.

We will do the preorder traversal to check the validation and use the inorder array to look for the left and right subtree. To access the index of the current root node, we will use the unordered_map because we can access the index of the root node in O(1) times. We will use recursion for this problem, and during the recursion, we need to check out the following conditions.

  • We will check whether the current element at preoder_index is present in the inorder vector.
     
  • We will check whether the inorder_index lies within the inorder_start and inorder_end range; if it does not, we will return false.
     
  • We will recursively check the above conditions for the left and right subtrees.
     

If we do not get a false as a return during the recursion, we can construct a binary tree with the help of preorder and inorder arrays.

Algorithm

  1. Initialize preorder_index as 0.
     
  2. If (inorder_start inorder_end), return true.
     
  3. Assign root the value of the element corresponding to preorder_index.
     
  4. Increment the preorder_index by 1.
     
  5. If the root is not present in the inorder vector, return false.
     
  6. Find out the inorder_index of the root using a map.
     
  7. Return false if inorder_index does not lie within the inorder_start and inorder_end range.
     
  8. Repeat the above steps for elements to the left of inorder_index, and check if the left subtree can be built using the inorder traversal.
     
  9. Repeat the above steps for elements to the right of inorder_index, and check if the right subtree can be built using the inorder traversal.

Implementation in C++

#include <bits/stdc++.h>
using namespace std;

// Function to find index of root node in inorder.
int findinorderIndex(unordered_map < int, int > & inorder_map, int root){
    return inorder_map[root];
}

// Function to check the construction of binary tree.
bool check(int inorder_start, int inorder_end, vector < int > preorder, int & preorder_index, unordered_map < int, int > & inorder_map) {
    if (inorder_start > inorder_end) {
        return true;
    }

    /* 
        Make the current element at preorder_index as root
        Increment preorder_index by one
    */
    int root = preorder[preorder_index];
    preorder_index = preorder_index + 1;

    // If root is not present in the inorder array, traversals are invalid
    if (inorder_map.find(root) == inorder_map.end()) {
        return false;
    }

    // Get the inorder_index from findinorderIndex function.
    int inorder_index = findinorderIndex(inorder_map,root);

    /* 
        If inorder_index does not lie within inorder_start 
        and inorder_end, traversals are invalid
    */
    if (inorder_start > inorder_index and inorder_index > inorder_end) {
        return false;
    }

    /* 
        Inorder_start_left and inorder_end_left are the start 
        and end indices of left subtree of root
    */
    int inorder_start_left = inorder_start;
    int inorder_end_left = inorder_index - 1;

    /* 
        Inorder_start_right and inorder_end_right are the start 
        and end indices of right subtree of root
    */
    int inorder_start_right = inorder_index + 1;
    int inorder_end_right = inorder_end;

    /* 
        If left subtree can not be built, return false 
        (no need to check for right subtree)
    */
    if (check(inorder_start_left, inorder_end_left, preorder, preorder_index, inorder_map)==false) {
        return false;
    } 
    else {
        return check(inorder_start_right, inorder_end_right, preorder, preorder_index, inorder_map);
    }
}

int main() {
    vector < int > preorder {
        10,
        20,
        40,
        50,
        30
    };
    vector < int > inorder {
        40,
        20,
        50,
        10,
        30
    };
    int n = 5;

    unordered_map < int, int > inorder_map;
    for (int i = 0; i < n; i++) {
        inorder_map[inorder[i]] = i;
    }

    int preorder_index = 0;
    bool res = check(0, n - 1, preorder, preorder_index, inorder_map);
    if (res) {
        cout << "Given input is valid to make a binary tree " << endl;
    } 
    else {
        cout << "Given input is invalid to make a binary tree " << endl;
    }
    return 0;
}


Output

c++ code output

Implementation in Java

import java.util.*;

public class Main
{
    static int preorder_index = 0;
    
    // Function to find index of root node in inorder.
    static int findinorderIndex( HashMap<Integer,Integer> inorderMap, int root){
        return inorderMap.get(root);
    }
    
    // Function to check the construction of binary tree.
    static boolean check(int inorder_start, int inorder_end, int preorder[], HashMap<Integer,Integer> inorderMap){
        
        // Base condition
        if(inorder_start > inorder_end){
            return true;
        }
        /* 
            Make the current element at preorder_index as root
            Increment preorder_index by one
        */
        int root = preorder[preorder_index];
        preorder_index = preorder_index + 1;
        
        // If root is not present in the inorder array, traversals are invalid
        if(inorderMap.containsKey(root)==false){
            return false;
        }
        
        // Get the inorder_index from findinorderIndex function.
        int inorder_index = findinorderIndex(inorderMap,root);
        
        /* 
            If inorder_index does not lie within inorder_start 
            and inorder_end, traversals are invalid
        */
        if (inorder_start > inorder_index && inorder_index > inorder_end) {
            return false;
        }
        
        /* 
            Inorder_start_left and inorder_end_left are the start 
            and end indices of left subtree of root
        */
        int inorder_start_left = inorder_start;
        int inorder_end_left = inorder_index - 1;
        
        /* 
            Inorder_start_right and inorder_end_right are the start 
            and end indices of right subtree of root
        */
        int inorder_start_right = inorder_index + 1;
        int inorder_end_right = inorder_end;
        
        /*
            If left subtree can not be built, return false 
            (no need to check for right subtree)
        */
        if (check(inorder_start_left, inorder_end_left, preorder, inorderMap)==false) {
        	return false;
        } 
        else {
        	return check(inorder_start_right, inorder_end_right, preorder, inorderMap);
        }
    }
    
    public static void main(String[] args) {
    	int preorder[] = {10,20,40,50,30};
        int inorder[] = {40,20,50,10,30};
        HashMap<Integer,Integer> inorderMap = new HashMap<Integer,Integer>();
        for(int i=0; i<preorder.length; i++){
            inorderMap.put(inorder[i],i);
        }
        
        boolean result = check(0,inorder.length - 1, preorder, inorderMap);

        if(result){
            System.out.println("Given input is valid to make a binary tree ");
        }
        else{
            System.out.println("Given input is invalid to make a binary tree ");
        }
	}
}


Output

java code output

Complexity Analysis

Time Complexity: O(N) as we do a preorder traversal of the tree using the preorder array. Here ‘N’ refers to the number of nodes in the tree.

Space Complexity: O(H) as we use recursion for the tree traversal. Here ‘H’ refers to the height of the tree.

Also check out - Inorder Predecessor

Frequently Asked Questions

What is a binary tree?

A binary tree is a data structure that stores the data in a hierarchal structure, and a binary tree parent nodes can have, at most, two nodes as children nodes.

What is preorder traversal?

It is one of the traversal methods of a binary tree in which we traverse the root node first, the left subtree of the root node, and then the right subtree.

What is inorder traversal?

In inorder traversal, we first traverse the left subtrees of the root node and then the root node, and after the root node, we traverse the right subtrees.

What is a root node?

The top node in the binary tree is known as the root node.

Can a binary tree have a zero node as a children node?

Yes, they can, it is the property of a binary tree that can have at most two nodes.

Conclusion

In this blog, we have discussed checking whether a tree's given preorder and inorder are valid for constructing a binary tree and implemented the solution with a dry run.

To learn more about programming check out the following links.

Recommended problems -

 

To learn more about DSA, competitive coding, and many more knowledgeable topics, please look into the guided paths on Coding Ninjas Studio. Also, you can enroll in our courses and check out the mock test and problems available to you. Please check out our interview experiences and interview bundle for placement preparations.

Happy Coding!

Previous article
Bottom-left to upward-right Traversal in a Binary Tree
Next article
Construct A Perfect Binary Tree From A Preorder Traversal
Live masterclass