Construct Binary Tree from Inorder and Postorder Traversal

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

Note:
You may assume that duplicates do not exist in the tree.

For example, given

inorder = [9,3,15,20,7]
postorder = [9,15,7,20,3]

Return the following binary tree:

    3
   / \
  9  20
    /  \
   15   7

Algorithm

  • Build hashmap value -> its index for inorder traversal.
  • Return buildTree function which takes as the arguments the left and right boundaries for the current subtree in the inorder traversal. These boundaries are used only to check if the subtree is empty or not. Here is how it works buildTree(l = 0, r = n - 1), where l = left and r = right.
    • If (left > right), the subtree is empty, return null.
    • Pick the last element in the postorder traversal as a root.
    • Root value has index inorder_index in the inorder traversal: 
      • Elements from left to inorder_index-1 belong to the left subtree.
      • Elements from inorder_index+1 to right belongs to the right subtree.
    • Following the postorder logic, proceed recursively  
      • First to construct the right subtree by buildTree(inorder_index + 1, right).
      • And then to construct the left subtree by buildTree(left, inorder_index - 1).
    • Return root.
class Solution {
    
    private int post_index = 0;
    private int[] inorder = null;
    private int[] postorder = null;
    private Map<Integer, Integer> inorderIndexMap = new HashMap<>();
    
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        
        this.inorder = inorder;
        this.postorder = postorder;
        
        for(int i = 0 ; i < inorder.length ; i++){
            inorderIndexMap.put(inorder[i], i);
        }
        post_index = postorder.length - 1;
        return buildTree(0, post_index);
    }
    
    private TreeNode buildTree(int l, int r){
        if( l > r){
            return null;
        }
        int cur_root_val = postorder[post_index--];
        TreeNode root = new TreeNode(cur_root_val);
        int inorder_index = inorderIndexMap.get(cur_root_val);
        root.right = buildTree(inorder_index + 1, r);
        root.left = buildTree(l, inorder_index-1);
        return root;
    }
}

Categories: Binary Tree

1 reply

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s