5.5 Construct Binary Tree from Preorder and Inorder Traversal

5.5.1 Problem Metadata

5.5.2 Description

Build a binary tree from preorder and inorder traversals.

5.5.3 Examples

Example 1: Balanced Tree

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output:
    3
   / \
  9  20
    /  \
   15   7
Explanation:
- Preorder: root first (3), then left subtree (9,20,15,7), ... wait that's wrong
- Preorder: 3 (root), 9 (left subtree root), 20 (right subtree root), 15, 7
- Inorder: 9 (left), 3 (root), 15,20,7 (right)

Example 2: Single Node

Input: preorder = [1], inorder = [1]
Output: 1

Example 3: Left-Skewed Tree

Input: preorder = [1,2,3], inorder = [3,2,1]
Output:
  1
 /
2
/
3

5.5.4 Constraints

  • 1 <= preorder.length <= 3000
  • inorder.length == preorder.length
  • -3000 <= preorder[i], inorder[i] <= 3000
  • preorder and inorder consist of unique values
  • Each value of inorder also appears in preorder
  • preorder is guaranteed to be a valid preorder traversal
  • inorder is guaranteed to be a valid inorder traversal

5.5.5 Solution - Hash Map with Divide and Conquer

5.5.5.1 Walkthrough

The key insight is that the first element of preorder is always the root. Once we find the root in inorder, we can divide the remaining elements into left and right subtrees:

  1. Preorder property: First element is always the root; remaining elements are [left subtree elements, right subtree elements]
  2. Inorder property: Elements are [left subtree elements, root, right subtree elements]
  3. Algorithm:
    • Take first element of preorder as root
    • Find its position in inorder
    • Elements to the left of root in inorder form the left subtree
    • Elements to the right of root in inorder form the right subtree
    • Recursively build left and right subtrees using the corresponding preorder and inorder subarrays
  4. Optimization: Use a HashMap to store inorder indices for O(1) root position lookup

5.5.5.2 Analysis

  • Time Complexity: O(n) — each node is visited once, and HashMap lookup is O(1)
  • Space Complexity: O(n) — HashMap stores all n values; recursion stack is O(h) where h is tree height

5.5.5.3 Implementation Steps

  1. Build a HashMap: value → index from the inorder array for fast lookup
  2. Define a recursive helper function that takes preorder bounds and inorder bounds
  3. In each recursion:
    • Extract root value from preorder[preL]
    • Find root position in inorder using HashMap
    • Calculate left subtree size = (root position in inorder) - inL
    • Recursively build left subtree: preorder[preL+1 to preL+leftSize], inorder[inL to rootPos-1]
    • Recursively build right subtree: preorder[preL+leftSize+1 to preR], inorder[rootPos+1 to inR]
  4. Base case: when preL > preR, return null

5.5.5.4 Code - Java

public TreeNode buildTree(int[] preorder, int[] inorder) {
    // inorder:  L -> Node -> R
    // preorder: Node -> L -> R

    // Map of inorder {val : index}
    Map<Integer, Integer> inIdxMap = new HashMap<>();
    for (int i = 0; i < inorder.length; i++) {
        inIdxMap.put(inorder[i], i);
    }
    return dfs(preorder, 0, preorder.length - 1, inIdxMap, 0);
}

private TreeNode dfs(int[] preorder, int preNode, int preR, Map<Integer, Integer> inIdxMap, int inL) {
    if (preNode > preR) {
        return null;
    }

    int nodeVal = preorder[preNode];
    TreeNode node = new TreeNode(nodeVal);
    int inNodeIdx = inIdxMap.get(nodeVal);

    // Left subtree from current node
    // inorder[] = [left subtree elements] [node] [right subtree elements]
    int lLength = inNodeIdx - inL;
    node.left = dfs(preorder, preNode + 1, preNode + lLength, inIdxMap, inL);
    node.right = dfs(preorder, preNode + lLength + 1, preR, inIdxMap, inNodeIdx + 1);

    return node;
}

5.5.5.5 Code - Golang

func buildTree(preorder []int, inorder []int) *TreeNode {
    // inorder:  L -> Node -> R
    // preorder: Node -> L -> R

    // Map of inorder {val : index}
    inIdxMap := make(map[int]int)

    for i, val := range inorder {
        inIdxMap[val] = i
    }

    root := dfs(preorder, 0, len(preorder) - 1, inIdxMap, 0)

    return root
}

func dfs(preorder []int, preNode int, preR int, inIdxMap map[int]int, inL int) *TreeNode {
    if preNode > preR {
        return nil
    }

    nodeVal := preorder[preNode]
    node := &TreeNode{Val: nodeVal}
    inNodeIdx := inIdxMap[nodeVal]

    // Left subtree from current node
    // inorder[] = [left subtree elements] [node] [right subtree elements]
    lLength := inNodeIdx - inL
    node.Left = dfs(preorder, preNode + 1, preNode + lLength, inIdxMap, inL)
    node.Right = dfs(preorder, preNode + lLength + 1, preR, inIdxMap, inNodeIdx + 1)

    return node
}