How to check if the given preorder ,inorder and postorder traversals are of the same binary tree?

Question

Currently I have the following algorithm which tries to create a tree from given inorder and preorder traversal and checks the postorder travesal of the tree so build with the given postorder?

But code seems to give runtime error! I am checking if a tree can even be made given the inorder and preorder traversal through a boolean possible.

My code to build tree is as below

    static TreeNode buildTree(int start,int end,int root_pos)
    {
        if(start>end)
            return null;

        int key=preorder.get(root_pos);
        TreeNode root=new TreeNode(key);

        int i=start;
        for(;i<=end;i++)
        {
            if(inorder.get(i)==key)
                break;
        }

        if(i>end) //Case when we couldn't find root in given inorder
        {
            possible=false; //this tree cannot be made from given inorder and preorder traversals
            return null;
        }
        else
        {
            root.left=buildTree(start, i-1, root_pos+1);
            root.right=buildTree(i+1, end, root_pos+i-start+1);
            return root;

        }

    }

What are the cases I am missing ?How can this be done?

I know how to construct tree from valid traversals,I want to know if the given traversals(which maybe invalid) are of the same tree?

The full problem statement is given here.

Dnyaneshwar Chavan Dnyaneshwar Chavan · Accepted Answer · 2020-04-12T01:00:07

Question says "check if the given preorder ,inorder and postorder traversals are of the same binary tree?". You are creating a tree from inorder and preorder and then checking its postorder traversal with given postorder. Here you are assuming that inorder and preorder will always be of same tree. Which is not necessarily true. Inoder and postorder might be of same tree and preorder might be of different tree. Hence your code is getting runtime error.

How to solve this problem: A tree can be created if inorder & preorder or inorder & postorder is given. Check below https://www.geeksforgeeks.org/construct-tree-from-given-inorder-and-preorder-traversal/ https://www.geeksforgeeks.org/construct-a-binary-tree-from-postorder-and-inorder/

Now for the current problem what we have to do is traverse tree formation logic from above two tree creation and see if we are landing at node with same value at every step. If at any step we encounter different values it means one of inorder, preorder or postorder traversal is incorrect. Pasting code to check the same below, if it helps

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 = {1, 5, 4, 2, 3};
        int[] in = {4, 2, 5, 1, 3};
        int[] post = {4, 1, 2, 3, 5};

        int res = test.solve(pre, in, post);
        System.out.print(res);
    }


    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);
    }

}

How to check if the given preorder ,inorder and postorder traversals are of the same binary tree?

1 Answers