Problem #105: Construct Binary Tree from Preorder and Inorder Traversal

Intuition & Strategy Breakdown

First element of preorder is root. Locate root in inorder list to partition left and right subtrees, recursively constructing tree.

Python Solution

def buildTree(preorder, inorder):
    inorder_map = {val: i for i, val in enumerate(inorder)}
    pre_idx = 0
    
    def helper(in_left, in_right):
        nonlocal pre_idx
        if in_left > in_right:
            return None
        
        root_val = preorder[pre_idx]
        root = TreeNode(root_val)
        pre_idx += 1
        
        mid = inorder_map[root_val]
        root.left = helper(in_left, mid - 1)
        root.right = helper(mid + 1, in_right)
        return root
        
    return helper(0, len(inorder) - 1)

Java Solution

class Solution {
    int pre_idx = 0;
    Map inorder_map = new HashMap<>();

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        for (int i = 0; i < inorder.length; i++) {
            inorder_map.put(inorder[i], i);
        }
        return helper(preorder, 0, inorder.length - 1);
    }

    private TreeNode helper(int[] preorder, int in_left, int in_right) {
        if (in_left > in_right) return null;

        int root_val = preorder[pre_idx++];
        TreeNode root = new TreeNode(root_val);
        int mid = inorder_map.get(root_val);

        root.left = helper(preorder, in_left, mid - 1);
        root.right = helper(preorder, mid + 1, in_right);
        return root;
    }
}