4.14.13 — Construct Binary Tree from Preorder and Inorder Traversal

LeetCode 105 · Medium · ★ Blind 75

The problem

Rebuild the tree from its pre-order and in-order traversals. All values are distinct.

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

     3
   /   \
  9    20
      /   \
    15     7

The pattern

Two facts, one from each traversal.

Pre-order visits the root first. So preorder[0] is the root of the whole tree. That is the only thing pre-order tells you directly, and it is enough.

In-order visits the left subtree, then the root, then the right subtree. So once you know which value is the root, finding it in inorder splits the array cleanly: everything to its left belongs to the left subtree, everything to its right belongs to the right subtree.

Put them together:

preorder = [3, 9, 20, 15, 7]
            ↑ root

inorder  = [9, 3, 15, 20, 7]
            └┘  ↑  └──────┘
           left root  right

Now you know the left subtree has 1 node and the right subtree has 3. And because pre-order lists the root, then all of the left subtree, then all of the right subtree, that size splits preorder too:

preorder = [3 | 9 | 20, 15, 7]
          root  left    right

Two subproblems of the same shape. Recurse.

The size from inorder is what tells you where to cut preorder. That is the one connection to hold on to.

Why two traversals are needed

A single traversal does not determine a tree. Both of these give pre-order [1, 2]:

  1        1
 /          \
2            2

Pre-order alone tells you the root but not where the left subtree ends. In-order alone tells you the split but not which value is the root. Together they are enough.

Pre-order plus post-order is not enough for a general binary tree, because neither says where the left subtree stops when a node has only one child. It works only if every node has 0 or 2 children.

The naive solution

def buildTree(self, preorder, inorder):
    if not preorder:
        return None
    root = TreeNode(preorder[0])
    mid = inorder.index(preorder[0])
    root.left = self.buildTree(preorder[1:mid+1], inorder[:mid])
    root.right = self.buildTree(preorder[mid+1:], inorder[mid+1:])
    return root

Correct, and pleasantly short. Two things make it slow:

• inorder.index(...) is a linear scan, done once per node → O(n^2).
• The slices copy arrays at every level → another O(n^2) and heavy allocation.

The linear solution

Fix both problems. Replace the scan with a hash map from value to its index in inorder, and replace the slices with index ranges.

Python

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        position = {val: i for i, val in enumerate(inorder)}     # value → index
        self.pre = 0                                             # next root to place

        def build(left: int, right: int):
            if left > right:
                return None

            value = preorder[self.pre]
            self.pre += 1

            node = TreeNode(value)
            mid = position[value]

            node.left = build(left, mid - 1)      # must be built FIRST
            node.right = build(mid + 1, right)
            return node

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

TypeScript

function buildTree(preorder: number[], inorder: number[]): TreeNode | null {
  const position = new Map<number, number>();
  inorder.forEach((v, i) => position.set(v, i));
  let pre = 0;

  function build(left: number, right: number): TreeNode | null {
    if (left > right) return null;

    const value = preorder[pre++];
    const node = new TreeNode(value);
    const mid = position.get(value)!;

    node.left = build(left, mid - 1);
    node.right = build(mid + 1, right);
    return node;
  }

  return build(0, inorder.length - 1);
}

The single moving pointer into preorder is the trick that removes the arithmetic. Instead of computing which slice of preorder belongs to each subtree, just consume it in order. Pre-order is defined as root, then the whole left subtree, then the whole right subtree — which is exactly the order the recursion asks for values.

So the left call must come before the right call. Swap those two lines and the pointer hands the right subtree values that belong to the left one, and the tree comes out wrong with no error message. This is the only line in the solution that can silently break.

left > right means an empty range, which is the base case.

Complexity

O(n) time — the map is built once, each node is created once, and each lookup is O(1).

O(n) space for the map, plus O(h) for the recursion.

Where this goes next

• Construct from Inorder and Postorder (LeetCode 106) — post-order visits the root last, so consume postorder from the back and build the right subtree first. A neat mirror image, and a good check that you understood why the order matters here.
• Construct from Preorder and Postorder — only possible when every node has 0 or 2 children.
• Serialize and Deserialize — a single pre-order traversal is enough if you write markers for the empty children, which is the whole idea of 4.14.15.

The rule: pre-order gives you the root, in-order gives you the split, and the size of the split tells you where to cut the other array.

What the interviewer will push on

"Why are two traversals needed?" Give the two-node counterexample.

"Why is the naive version O(n^2)?" The linear index search plus the array copying.

"Why must the left call come before the right?" The preorder pointer only moves forward, and pre-order lists the whole left subtree before the right.

"What about preorder and postorder?" Ambiguous unless every node has 0 or 2 children.

"What changes for inorder and postorder?" Consume from the back and build right first.

One thing to volunteer: state the two facts before writing code — "pre-order gives the root, in-order gives the split" — and then say that the split size is what cuts the pre-order array. That is the derivation, and it takes fifteen seconds.

Next: 4.14.14 Binary Tree Maximum Path Sum — the return-one-record-another structure from 4.14.3, made harder by negative numbers.