Repository navigation
088 — Construct Binary Tree from Preorder and Inorder Traversal
LeetCode 105 · Medium. Given two integer arrays preorder and inorder representing the preorder and inorder traversal of the same binary tree (with no duplicate values), reconstruct and return the tree.
Preorder traversal always visits the root first — so preorder[0] is always the root of whatever tree (or subtree) you're currently reconstructing. Inorder traversal, on the other hand, visits the root somewhere in the middle — everything before it in the inorder array belongs to the left subtree, and everything after it belongs to the right subtree. Put those two facts together: find the root's value from the front of preorder, locate that same value inside inorder to learn the split between left and right, and recurse on each half — using the corresponding slice of preorder for each side.
"Reconstruct a tree from preorder + inorder" is the cue to combine "preorder's first element is always the current subtree's root" with "inorder's split point around that same value tells you the left/right subtree boundary." The one thing to watch for: finding that split point requires searching inorder for the root's value — and how you do that search is exactly what separates a brute-force O(n²) solution from an O(n) one.
At every recursive call, take the first element of the current preorder slice as the root, then use firstIndex(of:) to scan the current inorder slice for that value from scratch — an O(n) scan repeated at every one of the n calls.
class TreeNode {
var val: Int
var left: TreeNode?
var right: TreeNode?
init(_ val: Int) { self.val = val }
}
func buildTreeBruteForce(_ preorder: [Int], _ inorder: [Int]) -> TreeNode? {
guard !preorder.isEmpty else { return nil }
let rootVal = preorder[0]
let root = TreeNode(rootVal)
guard let mid = inorder.firstIndex(of: rootVal) else { return root }
let leftInorder = Array(inorder[0..<mid])
let rightInorder = Array(inorder[(mid + 1)...])
let leftPreorder = Array(preorder[1..<(1 + leftInorder.count)])
let rightPreorder = Array(preorder[(1 + leftInorder.count)...])
root.left = buildTreeBruteForce(leftPreorder, leftInorder)
root.right = buildTreeBruteForce(rightPreorder, rightInorder)
return root
}
// smoke test: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
// 3
// / \
// 9 20
// / \
// 15 7
let bfTree = buildTreeBruteForce([3, 9, 20, 15, 7], [9, 3, 15, 20, 7])
print(bfTree?.val ?? -1, bfTree?.left?.val ?? -1, bfTree?.right?.val ?? -1) // 3 9 20
print(bfTree?.right?.left?.val ?? -1, bfTree?.right?.right?.val ?? -1) // 15 7Big-O: O(n²) time in the worst case — each of the n recursive calls performs an O(n) firstIndex(of:) scan (plus O(n) array-slicing work building the four sub-arrays), giving the same 1 + 2 + ... + n blowup seen in Diameter of Binary Tree, but here driven by repeated linear search instead of repeated height recomputation. O(n) extra space for all the sliced sub-arrays created along the way.
Precompute a value-to-index map over inorder once, up front, so every subtree's root position can be looked up in O(1). Track a moving pointer into preorder (since preorder always hands you the next root in order) and pass only index ranges into inorder, instead of slicing new arrays at every call.
func buildTree(_ preorder: [Int], _ inorder: [Int]) -> TreeNode? {
var preorderIndex = 0
var inorderIndexOf: [Int: Int] = [:]
for (i, val) in inorder.enumerated() {
inorderIndexOf[val] = i
}
func build(_ inorderLeft: Int, _ inorderRight: Int) -> TreeNode? {
guard inorderLeft <= inorderRight else { return nil }
let rootVal = preorder[preorderIndex]
preorderIndex += 1
let root = TreeNode(rootVal)
let mid = inorderIndexOf[rootVal]!
root.left = build(inorderLeft, mid - 1) // must build left before right —
root.right = build(mid + 1, inorderRight) // preorderIndex only advances correctly in this order
return root
}
return build(0, inorder.count - 1)
}
// smoke test: same traversal as above
let tree = buildTree([3, 9, 20, 15, 7], [9, 3, 15, 20, 7])
print(tree?.val ?? -1, tree?.left?.val ?? -1, tree?.right?.val ?? -1) // 3 9 20
print(tree?.right?.left?.val ?? -1, tree?.right?.right?.val ?? -1) // 15 7
// single node
let singleNode = buildTree([42], [42])
print(singleNode?.val ?? -1) // 42
print(buildTree([], []) == nil) // true — empty traversal arrays produce an empty treeBig-O: O(n) time — the map is built in one O(n) pass, and each of the n recursive calls now does O(1) work to find its root's split point instead of an O(n) scan. O(n) extra space for the map (plus O(h) for the recursion stack).
The brute force re-derives the same piece of information — "where does this value sit inside inorder?" — from scratch at every recursive call, via a linear scan each time. That information doesn't change across calls, though: it's a fixed mapping from value to index that can be computed once, up front, in a single pass. Precomputing it turns every subsequent "where's the split point" lookup into an O(1) hash map access instead of an O(n) scan — the exact same "don't recompute what you can precompute and reuse" idea that shows up across all these O(n²) -> O(n) tree problems, just applied to a lookup instead of a recursive height.
- Binary Trees — the tree being reconstructed, one subtree at a time.
-
Hash Maps & Hash Sets — the value-to-index map that turns each root lookup into
O(1)work. - DFS and Backtracking — the recursive "build the root, then build the left subtree, then build the right subtree" shape.
Construct Binary Tree from Preorder and Inorder is "preorder tells you who's the root, inorder tells you where the split is" — precompute a value-to-index map once, so finding that split never costs more than a single hash lookup.
Using preorder = [3, 9, 20, 15, 7] and inorder = [9, 3, 15, 20, 7], trace the optimal build function. Write down the value of preorderIndex and the (inorderLeft, inorderRight) range passed into each recursive call, in the order the calls happen. Why must root.left = build(...) be evaluated before root.right = build(...) for preorderIndex to stay correct?
⬅️ Previous: Kth Smallest Element in a BST · Next: Binary Tree Maximum Path Sum ➡️