Construct Binary Tree from Postorder and Inorder Traversal

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

Solution:

The post order array contains the elements in the order of post order traversal of the binary tree and we know that the last element in the post 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 post-order array. Recursively, we can build up the tree.

Implementation

public class CrazyForCode {
    int postIndex=0;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if(postorder.length==0) return null;
        postIndex = postorder.length-1;
        return buildBTree(inorder,postorder,0,postorder.length-1,0,postorder.length-1);
    }
    
    public TreeNode buildBTree(int[] inorder, int[] postorder, int start,int end, int pstart,int pend){
        if(start>end || pstart>pend) return null;
        TreeNode node = new TreeNode(postorder[pend]);
        int inorderIndex = getInorderIndex(inorder, postorder[pend]);
        
        node.left= buildBTree(inorder,postorder,start,inorderIndex-
        1,pstart,pstart+inorderIndex-(start+1));
        
        node.right = buildBTree(inorder,postorder,inorderIndex+
        1,end,pstart+inorderIndex-start,pend-1);
        
        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;
    }
}