106. Construct Binary Tree from Inorder and Postorder Traversal

Intuition

The last element in the postorder traversal is the root of the tree. By finding this root in the inorder traversal, we can determine the boundaries of the left and right subtrees. This process can be repeated recursively for each subtree.

Approach

1. Use a dictionary to map each value in the inorder traversal to its index for quick lookup.
2. Define a recursive function build that takes the start and end indices of the current subtree in the inorder traversal.
3. In each call to build: - Pop the last element from the postorder list, which is the root of the current subtree. - Create a new TreeNode with this value. - Find the index of this value in the inorder list using the dictionary. - Recursively build the right subtree (elements after the root in the inorder list). - Recursively build the left subtree (elements before the root in the inorder list).
4. Return the root of the constructed tree.

Complexity

Time Complexity:

O(N), where N is the number of nodes in the tree. Each node is processed once.

Space Complexity:

O(N), to store the dictionary and the recursive call stack.

Code

C++

class Solution {
public:
    TreeNode* buildTree(vector& inorder, vector& postorder) {
        int idx = postorder.size() - 1;
        unordered_map map;
        
        for (int i = 0; i < inorder.size(); ++i) {
            map[inorder[i]] = i;
        }

        return build(inorder, postorder, map, idx, 0, inorder.size() - 1);
    }
private:
    TreeNode* build(vector& inorder, vector& postorder, unordered_map& map, int& idx, int start, int end) {
        if (start > end) return nullptr;

        TreeNode* node = new TreeNode(postorder[idx--]);

        node->right = build(inorder, postorder, map, idx, map[node->val] + 1, end);
        node->left = build(inorder, postorder, map, idx, start, map[node->val] - 1);

        return node;
    }
};

Python

class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
        if not inorder or not postorder:
            return None

        # Dictionary to store the index of each value in inorder traversal
        idx_map = {val: idx for idx, val in enumerate(inorder)}

        def build(start, end):
            if start > end:
                return None
            # Last element in postorder is the root of current tree/subtree
            root_val = postorder.pop()
            root = TreeNode(root_val)

            # Split the tree into left and right subtrees using the inorder index
            idx = idx_map[root_val]
            
            # Build right subtree before left subtree
            root.right = build(idx + 1, end)
            root.left = build(start, idx - 1)

            return root

        return build(0, len(inorder) - 1)

Java

class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) 
    {
        Map map = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }
        return build(inorder, postorder, map, postorder.length - 1, 0, inorder.length - 1);
    }
    private TreeNode build(int[] inorder, int[] postorder, Map map, int postIdx, int inStart, int inEnd) {
        if (inStart > inEnd) {
            return null;
        }

        TreeNode root = new TreeNode(postorder[postIdx]);
        int inIdx = map.get(postorder[postIdx]);

        root.right = build(inorder, postorder, map, postIdx - 1, inIdx + 1, inEnd);
        root.left = build(inorder, postorder, map, postIdx - (inEnd - inIdx) - 1, inStart, inIdx - 1);

        return root;
    }
}

JavaScript

var buildTree = function(inorder, postorder) 
{
    
    let idx = postorder.length-1
    let map = {}

    inorder.forEach((el, i) => map[el] = i)

    function build(start, end){
        if(start > end) return null

        let node = new TreeNode(postorder[idx--])


        node.right = build(map[node.val]+1, end)
        node.left = build(start, map[node.val]-1)

        return node
    }

    return build(0, inorder.length-1)
};