Construct Binary Tree from Preorder and Inorder Traversal (LC 105)

Pattern: Divide & Conquer on Inorder + Preorder Index
Difficulty: Medium
Key Concept: Preorder’s first element is the root; find that value in inorder to split left size vs right size; recurse on subranges.

Problem Statement

Given two integer arrays preorder and inorder where inorder is an inorder traversal of a binary tree and preorder is a preorder traversal of the same tree, reconstruct the tree and return its root.

Assumptions: preorder and inorder have the same length; values are unique (guarantees unique tree).

Example

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

Tree:

    3
   / \
  9  20
     / \
    15  7

---

1. Algorithm & Pseudocode

Brute force

1. Pick preorder[0] as root; scan inorder linearly each recursion to find index k — O(n) per level → O(n²) total skewed.
2. Slice new arrays for each call (copy) — extra O(n²) space.

Pseudocode

function build(pre, in):
    if pre empty: return null
    rootVal = pre[0]
    root = new Node(rootVal)
    k = indexOf(in, rootVal)          // O(n)
    root.left = build(pre[1:k+1], in[0:k])
    root.right = build(pre[k+1:], in[k+1:])
    return root

Optimal

1. Use a HashMap: value → index in inorder for O(1) lookup.
2. Maintain preIndex (or pass ranges) to take the next root from preorder without slicing.
3. Recurse on (inStart, inEnd) subrange in inorder.

Pseudocode

map = buildMap(inorder)
preIndex = 0

function helper(inStart, inEnd):
    if inStart > inEnd: return null
    rootVal = preorder[preIndex++]
    root = new Node(rootVal)
    mid = map[rootVal]
    root.left = helper(inStart, mid - 1)
    root.right = helper(mid + 1, inEnd)
    return root

return helper(0, n - 1)

---

2. Step-by-Step Analysis (Beginner-Friendly)

• Preorder is root, left…, right… — the next preorder value is always the root of the current inorder segment.
• Inorder is left…, root, right… — everything left of root in inorder belongs to the left subtree; right of root to the right subtree.
• Unique values ensure mid is unambiguous.
• Why HashMap: Linear search of mid every call dominates runtime; map removes that bottleneck.

---

3. The Dry Run

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

Inorder index map: 9→0, 3→1, 15→2, 20→3, 7→4

preIndex	rootVal	in range	mid	left range	right range
0	3	[0..4]	1	[0..0]	[2..4]
1	9	[0..0]	0	∅	∅ → leaf 9
2	20	[2..4]	3	[2..2]	[4..4]
3	15	[2..2]	2	∅	∅ → leaf 15
4	7	[4..4]	4	∅	∅ → leaf 7

ASCII result

      3
     / \
    9  20
       / \
      15  7

---

4. Java Solution

Brute Force

import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int v) { val = v; }
}

class SolutionBrute {
    // Time: O(n^2) worst skewed, Space: O(n^2) if copying slices; below avoids copy with indices but linear search
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return build(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
    }

    private TreeNode build(int[] pre, int ps, int pe, int[] in, int is, int ie) {
        if (ps > pe || is > ie) return null;
        int rootVal = pre[ps];
        TreeNode root = new TreeNode(rootVal);
        int mid = is;
        while (in[mid] != rootVal) mid++; // O(n) per node worst
        int leftSize = mid - is;
        root.left = build(pre, ps + 1, ps + leftSize, in, is, mid - 1);
        root.right = build(pre, ps + leftSize + 1, pe, in, mid + 1, ie);
        return root;
    }
}

Optimal

import java.util.HashMap;
import java.util.Map;

class Solution {
    private int preIdx;
    private Map<Integer, Integer> idx;

    // Time: O(n), Space: O(n) map + O(h) stack
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        idx = new HashMap<>(inorder.length);
        for (int i = 0; i < inorder.length; i++) idx.put(inorder[i], i);
        preIdx = 0;
        return dfs(preorder, 0, inorder.length - 1);
    }

    private TreeNode dfs(int[] pre, int inLo, int inHi) {
        if (inLo > inHi) return null;
        int val = pre[preIdx++];
        TreeNode root = new TreeNode(val);
        int mid = idx.get(val);
        root.left = dfs(pre, inLo, mid - 1);
        root.right = dfs(pre, mid + 1, inHi);
        return root;
    }
}

---

5. The “Java vs. Others” Edge

• HashMap<Integer,Integer> with initial capacity inorder.length reduces rehashing.
• preIdx as a field (or single-element array) is idiomatic Java because inner methods cannot reassign outer int without a holder.
• Do not use Arrays.copyOfRange in tight loops on large inputs — it allocates O(n) per call.

---

6. Complexity Summary

Approach	Time	Space	Notes
Brute (linear search mid)	O(n²)	O(h)	Quadratic when tree is skewed
HashMap + index preorder	O(n)	O(n)	One pass build map; each node created once