Construct Binary Tree from Preorder and Inorder — HashMap Index

Problem 369 · Construct Binary Tree from Preorder and Inorder Traversal

Difficulty: Medium · Pattern: Divide and Conquer + HashMap

Intuition

preorder[0] is the root
Find root in inorder → left size and right size
Recurse on left and right slices

Use a HashMap for O(1) inorder lookup.

Solutions

# Python
def buildTree(preorder, inorder):
    idx_map = {val:i for i,val in enumerate(inorder)}
    pre_idx = [0]
    def build(lo, hi):
        if lo > hi: return None
        root_val = preorder[pre_idx[0]]; pre_idx[0] += 1
        root = TreeNode(root_val)
        mid = idx_map[root_val]
        root.left = build(lo, mid-1)
        root.right = build(mid+1, hi)
        return root
    return build(0, len(inorder)-1)

// Java
Map<Integer,Integer> idxMap=new HashMap<>(); int[] pre; int preIdx=0;
public TreeNode buildTree(int[] preorder, int[] inorder) {
    pre=preorder;
    for (int i=0;i<inorder.length;i++) idxMap.put(inorder[i],i);
    return build(0,inorder.length-1);
}
TreeNode build(int lo, int hi) {
    if (lo>hi) return null;
    int val=pre[preIdx++], mid=idxMap.get(val);
    TreeNode root=new TreeNode(val);
    root.left=build(lo,mid-1);
    root.right=build(mid+1,hi);
    return root;
}

Complexity

Time: O(n)
Space: O(n)