Construct Binary Tree from Preorder and Inorder Traversal Solution

Problem

Given the preorder and inorder traversal sequences of a binary tree, reconstruct the original tree. Every node value is unique, so the root can always be unambiguously identified.

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

Input: preorder = [3, 9, 20, 15, 7], inorder = [9, 3, 15, 20, 7]
Output: The root of the reconstructed tree shown above
Explanation: 3 is the root (first in preorder); in inorder, all values left of 3 form the left subtree and all values right of 3 form the right subtree.

Intuition

Preorder traversal always visits the root first, so preorder[0] is the root of the current subtree. Once we know the root, we can locate it in the inorder array — everything to its left belongs to the left subtree and everything to its right belongs to the right subtree. The size of the left subtree tells us exactly how many elements to take from the remaining preorder array for the left branch, and the rest go to the right branch. We recurse until there are no more elements.

Approach 1 — Recursive with Linear Scan

For each call, scan the inorder array to find the root's position. Simple to reason about, but the linear scan per node makes it O(n²) overall.

The first element of the current preorder slice is the root value.
Scan inorder left-to-right until the root value is found at index mid.
The left subtree covers inorder[:mid] — its size tells us preorder[1:1+mid] feeds the left subtree.
The right subtree covers inorder[mid+1:] and preorder[1+mid:].
Recurse on both halves, linking the results as left and right children.
Return the root node.

1class Solution:
2    def buildTree(self, preorder: list[int], inorder: list[int]) -> TreeNode | None:
3        if not preorder:
4            return None
5
6        root_val = preorder[0]
7        root = TreeNode(root_val)
8
9        mid = inorder.index(root_val)  # O(n) scan — the bottleneck
10
11        root.left = self.buildTree(preorder[1:1 + mid], inorder[:mid])
12        root.right = self.buildTree(preorder[1 + mid:], inorder[mid + 1:])
13        return root

Time: O(n²) — finding the root in inorder costs O(n) for each of the n nodes.
Space: O(n) — the call stack can reach depth n for a skewed tree.

Approach 2 — Recursive with Index Map

Pre-build a hashmap from each value to its inorder index so every lookup is O(1). Advance a single global index into preorder as each node is created — this avoids recomputing slice boundaries.

Build inorder_map: value → its index in inorder (one-time O(n) pass).
Keep a single preorder_pos counter pointing to the next root to consume.
Recursive function takes only inorder bounds [in_left, in_right].
The current root is preorder[preorder_pos]; increment the counter.
Look up the root's inorder index in O(1), then recurse left before right — left must come first because preorder visits the entire left subtree before the right.
Return the root node.

1class Solution:
2    def buildTree(self, preorder: list[int], inorder: list[int]) -> TreeNode | None:
3        inorder_map = {val: idx for idx, val in enumerate(inorder)}
4        preorder_pos = [0]  # list so the nested function can mutate it
5
6        def build(in_left: int, in_right: int) -> TreeNode | None:
7            if in_left > in_right:
8                return None
9
10            root_val = preorder[preorder_pos[0]]
11            preorder_pos[0] += 1
12            root = TreeNode(root_val)
13
14            in_root = inorder_map[root_val]  # O(1) lookup
15
16            # left before right — preorder visits left subtree first
17            root.left  = build(in_left, in_root - 1)
18            root.right = build(in_root + 1, in_right)
19            return root
20
21        return build(0, len(inorder) - 1)

Time: O(n) — each node is processed once with O(1) lookup.
Space: O(n) — O(n) for the hashmap plus O(n) for the call stack.

Complexity Summary

Approach	Time	Space	When to use
Linear Scan	O(n²)	O(n)	Interviews where you want to show the naive approach first before optimizing
Index Map	O(n)	O(n)	Any practical use; default choice when input size is non-trivial

Common Mistakes

Forgetting leftSize when computing preorder boundaries — you cannot use the raw inorder root index as the preorder split; you need leftSize = inRootIdx - inLeft (the count of nodes in the left subtree) to correctly slice preorder into left and right halves.
Calling inorder.index() inside the recursion — this looks like a one-liner shortcut but is O(n) per call, silently turning an O(n) algorithm into O(n²). Precompute the hashmap once before any recursion begins.
Recursing right before left in the index-map approach — preorder visits the entire left subtree before the right, so preorderPos must advance through left-subtree nodes first; flipping the recursion order silently assigns wrong values to every right-subtree node.
Off-by-one in inorder bounds — the root itself is at inRootIdx and must not be included in either subtree; the left call uses [inLeft, inRootIdx - 1] and the right call uses [inRootIdx + 1, inRight], not inRootIdx.
Missing the base case for empty ranges — when in_left > in_right (or preLeft > preRight), there are no nodes left; returning None/nullptr immediately prevents an out-of-bounds read on the preorder array.

Construct Binary Tree from Preorder and Inorder Traversal — Solution