Week 4 · Trees

Construct Binary Tree from Preorder and Inorder Traversal

Reconstruct the unique binary tree whose preorder and inorder traversals are given, assuming all values are distinct.

Medium Trees Week 4 Practice runner

Frame the problem

Preorder gives the root before its subtrees.
Inorder gives the left subtree, root, then right subtree.
Values are distinct in the standard problem.

1. Reveal example inputs and outputs

Example 1

Input:

build_tree([
  3,
  9,
  20,
  15,
  7
], [
  9,
  3,
  15,
  20,
  7
])

Output:

[
  3,
  [
    9,
    null,
    null
  ],
  [
    20,
    [
      15,
      null,
      null
    ],
    [
      7,
      null,
      null
    ]
  ]
]

Example 2

Input:

build_tree([
  1
], [
  1
])

Output:

[
  1,
  null,
  null
]

2. Brute force first

How would you find the root and split the inorder list by hand for the first example?

3. Reveal the insight ladder

The next preorder value is always the root of the current subtree.
Find that root in inorder.
Everything left of that index belongs to the left subtree; everything right belongs to the right subtree.
Use an index map to avoid scanning inorder each time.

4. Dry run before code

preorder = [3, 9, 20, 15, 7], inorder = [9, 3, 15, 20, 7].
Root is 3.
Inorder splits left [9] and right [15, 20, 7].
Next preorder values recursively build the left and right subtrees.

5. Reveal final Python solution

def build_tree(preorder, inorder):
    index = {value: i for i, value in enumerate(inorder)}
    preorder_i = 0

    def build(left, right):
        nonlocal preorder_i
        if left > right:
            return None
        value = preorder[preorder_i]
        preorder_i += 1
        split = index[value]
        return [value, build(left, split - 1), build(split + 1, right)]

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

Complexity: Time O(n) with the inorder index map, space O(n) for the map plus O(h) recursion stack.

Interview narration

I will let preorder choose roots and inorder choose subtree boundaries.
The preorder pointer moves exactly once per created node.
The inorder bounds tell each recursive call which values belong to that subtree.

Common traps

Slicing lists repeatedly and turning O(n) logic into O(n^2) copying.
Forgetting that duplicate values break the simple value-to-index map.
Advancing the preorder pointer after building children instead of before.

Follow-up drills

1. Why do values need to be distinct?

The inorder index map needs one position per value. With duplicates, the same value can match multiple positions and the traversals no longer determine a unique tree without extra identity information.

2. Can preorder and postorder uniquely reconstruct a binary tree?

Not in general. They can be ambiguous unless the tree is constrained, for example as a full binary tree.

3. How do you reduce copying?

Pass integer bounds into the recursive function and keep one shared preorder pointer plus a value-to-inorder-index map.

Interactive runner

Write the required Python function. Your code runs locally in this browser. Hints reveal one failing case at a time.