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
    15     7

To put this in plain English: you are given two arrays. preorder is the list of node values obtained by visiting a tree in Root \rightarrow Left \rightarrow Right order. inorder is the list of node values obtained by visiting it in Left \rightarrow Root \rightarrow Right order. You must physically reconstruct the original tree and return its root.

Constraints to Keep in Mind:

• 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 the preorder traversal of the tree.
• inorder is guaranteed to be the inorder traversal of the tree.

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);
}

Code Walkthrough

1. position = {val: i for i, val in enumerate(inorder)}: Create a hash map so we can look up the index of any value in the inorder array in O(1) time. This is what makes the algorithm linear.
2. self.pre = 0: This is a global/instance pointer that tells us which element of preorder to process next. Because preorder always gives roots first, we can just consume it from left to right.
3. def build(left: int, right: int):: Our recursive helper takes the inclusive boundaries of the inorder array that belong to the current subtree.
4. if left > right: return None: Base case. The range is empty, so there is no node here.
5. value = preorder[self.pre]: Grab the root value for this subtree from preorder.
6. self.pre += 1: Advance the pointer so the next recursive call gets the next root.
7. node = TreeNode(value): Create the actual root node object.
8. mid = position[value]: Ask the hash map where this root value sits in the inorder array. Everything to the left of mid (from left to mid - 1) belongs to the left subtree. Everything to the right (from mid + 1 to right) belongs to the right subtree.
9. node.left = build(left, mid - 1): Recursively build the left child FIRST. It must be first because preorder lists all left-subtree roots before right-subtree roots.
10. node.right = build(mid + 1, right): Recursively build the right child.
11. return node: Return the constructed subtree back to its parent.
12. return build(0, len(inorder) - 1): Kick off the recursion with the full inorder range.

Hand Trace

preorder = [3, 9, 20, 15, 7], inorder = [9, 3, 15, 20, 7]position = {9:0, 3:1, 15:2, 20:3, 7:4}, pre = 0

1. build(0, 4):
   • value = preorder[0] = 3. pre becomes 1. mid = position[3] = 1.
   • node = 3.
   • node.left = build(0, 0)
   • node.right = build(2, 4)
2. build(0, 0) (left of 3):
   • value = preorder[1] = 9. pre becomes 2. mid = position[9] = 0.
   • node = 9.
   • node.left = build(0, -1) \rightarrow returns None.
   • node.right = build(1, 0) \rightarrow returns None.
   • Returns node 9. 3.left = 9.
3. build(2, 4) (right of 3):
   • value = preorder[2] = 20. pre becomes 3. mid = position[20] = 3.
   • node = 20.
   • node.left = build(2, 2)
   • node.right = build(4, 4)
4. build(2, 2) (left of 20):
   • value = preorder[3] = 15. pre becomes 4. mid = position[15] = 2.
   • node = 15. Returns node 15. 20.left = 15.
5. build(4, 4) (right of 20):
   • value = preorder[4] = 7. pre becomes 5. mid = position[7] = 4.
   • node = 7. Returns node 7. 20.right = 7.

Tree fully built! ✓

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

• Time Complexity: O(n). We iterate through the n elements of inorder once to build the hash map (O(n)). Then we make exactly one build call for each of the n elements in preorder. Each call takes O(1) time to do hash map lookups, array indexing, and object creation. O(n) + O(n) = O(n).
• Space Complexity: O(n) extra space. The hash map takes O(n) space to store n key-value pairs. The recursion stack uses O(h) space, where h is the height of the tree. Since h \le n, the dominant term is O(n).

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.