Check whether the given Preorder, Inorder and Postorder traversals are of the same tree or not

Optimized Approach

In this approach, for the construction of the tree using Inorder and Preorder traversals we will check whether a valid binary tree can be formed using these traversals or not. If such a tree can be formed then we will continue our iterations and if the tree cannot be formed then we will stop building the tree further. Also, we will use a hashmap to store the indices of the inorder elements in the array to make our code more efficient.

Pseudocode

The pseudocode is as follows:

1. Take the input of the order traversals and store each traversal order in an array, say inOrder[], preOrder[], and postOrder[].
2. Now, to construct a tree out of the two given orders, pick an initial element from preOrder[] and increment a preorder index variable to pick the following element in the next recursive call of the function.
3. Create a new tree node with the data of the element picked up in the previous step 
4. Find the chosen element in the inOrder[] array and store the inorder index using a hashmap and check whether a valid tree node can be created or not. In order to check for a valid binary tree, use the conditions of the binary tree to check if the chosen element is valid or not..
5. Call the function to build the tree for elements before the inorder index and make it as the left subtree of the tree node.
6. Call the function to build the tree for elements after the inorder index and make it as the right subtree of the tree node.
7. Return the tree node.

Implementation

C++ Code:

// Program to check whether the given preorder, inorder and postorder traversals are of the same tree or not
#include <bits/stdc++.h>
using namespace std;
struct Tnode {
    int info;
    Tnode *left, *right;
 
    Tnode(int val)
    {
        info = val;
        left = right = NULL;
    }
};
Tnode* buildTreeFromInorderPreorder(
    int inStart, int inEnd, int& preIndex, int preorder[],
    unordered_map<int, int>& inorderIndexMap,
    bool& notPossible)
{
    if (inStart > inEnd)
        return NULL;
 
    // build the current Tnode
    int rootData = preorder[preIndex];
    Tnode* root = new Tnode(rootData);
    preIndex++;
 
    // find the node in inorderIndexMap
    if (inorderIndexMap.find(rootData)
        == inorderIndexMap.end()) {
        notPossible = true;
        return root;
    }
 
    int inorderIndex = inorderIndexMap[rootData];
    if (!(inStart <= inorderIndex
          && inorderIndex <= inEnd)) {
        notPossible = true;
        return root;
    }
 
    int leftInorderStart = inStart,
        leftInorderEnd = inorderIndex - 1,
        rightInorderStart = inorderIndex + 1,
        rightInorderEnd = inEnd;
 
    root->left = buildTreeFromInorderPreorder(
        leftInorderStart, leftInorderEnd, preIndex,
        preorder, inorderIndexMap, notPossible);
 
    if (notPossible)
        return root;
 
    root->right = buildTreeFromInorderPreorder(
        rightInorderStart, rightInorderEnd, preIndex,
        preorder, inorderIndexMap, notPossible);
 
    return root;
}
 
bool checkPostorderCorrect(Tnode* root, int& postIndex,
                          int postorder[])
{
    if (!root)
        return true;
 
    if (!checkPostorderCorrect(root->left, postIndex,
                              postorder))
        return false;
    if (!checkPostorderCorrect(root->right, postIndex,
                              postorder))
        return false;
 
    return (root->info == postorder[postIndex++]);
}
 
void printPostorder(Tnode* root)
{
    if (!root)
        return;
 
    printPostorder(root->left);
    printPostorder(root->right);
 
    cout << root->info << ", ";
}
 
void printInorder(Tnode* root)
{
    if (!root)
        return;
 
    printInorder(root->left);
    cout << root->info << ", ";
    printInorder(root->right);
}
 
bool checktree(int preorder[], int inorder[],
              int postorder[], int N)
{
    // Your code goes here
    if (N == 0)
        return true;
 
    unordered_map<int, int> inorderIndexMap;
    for (int i = 0; i < N; i++)
        inorderIndexMap[inorder[i]] = i;
 
    int preIndex = 0;
 
    // return checkInorderPreorder(0, N - 1, preIndex,
    // preorder, inorderIndexMap) &&
    // checkInorderPostorder(0, N - 1, postIndex, postorder,
    // inorderIndexMap);
 
    bool notPossible = false;
 
    Tnode* root = buildTreeFromInorderPreorder(
        0, N - 1, preIndex, preorder, inorderIndexMap,
        notPossible);
 
    if (notPossible)
        return false;
 
    int postIndex = 0;
 
    return checkPostorderCorrect(root, postIndex,
                                postorder);
}
 
// Driver program to test above functions
int main()
{
    int inOrder[] = { 10, 20, 15, 25, 30 };
    int preOrder[] = { 25, 20, 10, 15, 30 };
    int postOrder[] = { 10, 15, 20, 30, 25 };
 
    int len = sizeof(inOrder) / sizeof(inOrder[0]);
 
    // If both postorder traversals are same
    if (checktree(preOrder, inOrder, postOrder, len))
        cout << "Yes, the traversals are of the same tree";
    else
        cout << "No, the traversals are not of the same tree";
 
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Java Code:

// Program to check whether the given preorder, inorder and postorder traversals are of the same tree or not
import java.util.HashMap;
import java.util.Map;

public class Test {
    int res;

    public static void main(String[] args) {
        Test test = new Test();

        int[] pre = { 25, 15, 10, 20, 30 };
        int[] in = { 10, 20, 15, 25, 30 };
        int[] post= { 10, 25, 20, 30, 15 };

        int res = test.solve(pre, in, post);
        if(res==0)
        {
            System.out.print("Yes,the traversals are of the same tree");
        }
        else
        {
            System.out.print("No,the traversals are not of the same tree");
        }
    }


    public int solve(int[] A, int[] B, int[] C) {
        if (A.length != B.length || B.length != C.length)
            return 0;

        res = 1;
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < B.length; i++)
            map.put(B[i], i);

        util(A, map, C, 0, B.length - 1, 0, C.length - 1);
        return res;
    }

    private void util(int[] pre, Map<Integer, Integer> map, int[] post,      int inStart, int inEnd, int preIndex, int postIndex) {
        if (inStart > inEnd)
            return;

        Integer mid = map.get(pre[preIndex]);
        if (mid == null || pre[preIndex] != post[postIndex]) {
            res = 0;
            return;
        }

        // check for left part of tree
        util(pre, map, post, inStart, mid - 1, preIndex + 1, postIndex - (inEnd - mid) - 1);

        // check for right part of tree
        util(pre, map, post, mid + 1, inEnd, preIndex + (mid - inStart) + 1, postIndex - 1);
    }
}

You can also try this code with Online Java Compiler

Run Code

Output: Yes, the traversals are of the same tree

Complexity Analysis

Time Complexity: In the optimized approach, we have made the program efficient by using a hashmap to store the inorder array indices and therefore, only n nodes were traversed giving us a time complexity of O(n).

Space Complexity: The space complexity of the program remains the same, i.e. of the order O(n) for storing n nodes.
Check out this problem - Largest BST In Binary Tree

Frequently Asked Questions

Which traversal order is used to create a copy of the tree and which is used for deletion of the tree?

Preorder traversal helps in creating a copy of the tree and Postorder traversal helps in deletion of the tree.

What is the level order traversal and when is it used?

Level order traversal in a tree follows the breadth-first approach to visit the nodes of a tree and it is used when we need to traverse all the nodes at the same level first from left to right and then move onto the next level of nodes.

In binary trees, how can we get nodes in non-decreasing order?

Inorder traversal gives the nodes in non-decreasing order in a binary tree.

Conclusion

This article discussed the approach to check whether the given preorder, inorder and postorder traversals are of the same tree or not. We have also implemented the pseudocode for checking whether the given preorder, inorder and postorder traversals are of the same tree or not in Python and C++.

Recommended problems -

• Preorder Traversal
• Zig Zag Tree Traversal 

Refer to our guided paths on Coding Ninjas Studio to upskill yourself in Data Structures and Algorithms, Competitive Programming, JavaScript, System Design, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But if you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc; you must have a look at the problems, interview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!