Construct Tree from given Preorder and Inorder Traversals

Given preorder and inorder traversal of a tree, construct the binary tree.

Solution:

The pre order array contains the elements in the order of pre order traversal of the binary tree and we know that the first element in the pre order traversal is the root of the binary tree. We can then search the root element in inorder traversal of the tree. Then we can identify the left and right subtrees of the root from inorder array.

Using the length of left sub-tree, we can identify left and right subtrees in pre-order array. Recursively, we can build up the tree.

Implementation:

public class CrazyForCOde {
    int preIndex=0;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(inorder.length==0) 
            return null;
        return buildBTree(preorder,inorder,0,inorder.length-1);
    }
    
    public TreeNode buildBTree(int[] preorder, int[] inorder, int start, int end){
        
        if(start>end)
        { 
            return null;
        }

        TreeNode node = new TreeNode(preorder[preIndex]);
        int inorderInd=getInorderIndex(inorder, preorder[preIndex]);
        preIndex++;

        node.left = buildBTree(preorder,inorder,start,inorderInd-1);
        node.right = buildBTree(preorder,inorder,inorderInd+1,end);

        return node;
        
    }
    
    public int getInorderIndex(int[] inorder, int target){
        for(int i=0; i<inorder.length;i++){
            if(inorder[i]==target){
                return i;
            }
        }
        return -1;
    }
}