Construct Binary Tree from Preorder and Inorder Traversal (LeetCode 105)
A binary tree whose values are all different was walked twice, and each walk wrote its values into a list.
preorderlists every subtree as its root first, then its left subtree, then its right subtree.inorderlists every subtree as its left subtree first, then its root, then its right subtree.
Both lists describe the same tree and hold the same values. Rebuild that tree and return its root.
Worked Examples
preorder = [3,9,20,15,7], inorder = [9,3,15,20,7][3,9,20,null,null,15,7]preorder = [-1], inorder = [-1][-1]⚖️Formal Constraints & Bounds
1 <= preorder.length <= 3000inorder.length == preorder.length-3000 <= preorder[i], inorder[i] <= 3000The values in
preorderare distinct, and so are the values ininorder.Every value of
inorderalso appears inpreorder.preorderis the tree's preorder traversal andinorderis the same tree's inorder traversal.
Core Insight
Preorder gives each subtree's root before anything else in it, and inorder puts that root between its two subtrees. So the next unused preorder value is the root, its inorder index splits the range, and building the left side first keeps the preorder cursor on the right root for the right side.
Real-World Scenario & Production Applications
Tree-shaped data is often stored as a flat list and read back later: a listing of folders written parent-first is a preorder, and so is the order in which many serializers write an object tree. One order alone can't give back the shape; a second order, or a marker for every missing child, can. Restoring a saved tree from such listings is this problem.
Step-by-Step Execution Trace Table
Example 1, preorder = [3,9,20,15,7], inorder = [9,3,15,20,7], so where = {9: 0, 3: 1, 15: 2, 20: 3, 7: 4}. Each row is one build(lo, hi) that makes a node, in the order the calls run:
| Step | Call | pre_idx | root | mid | Left range | Right range |
|---|---|---|---|---|---|---|
| 1 | build(0, 4) | 0 | 3 | 1 | inorder[0..0] = [9] | inorder[2..4] = [15, 20, 7] |
| 2 | build(0, 0) | 1 | 9 | 0 | empty | empty |
| 3 | build(2, 4) | 2 | 20 | 3 | inorder[2..2] = [15] | inorder[4..4] = [7] |
| 4 | build(2, 2) | 3 | 15 | 2 | empty | empty |
| 5 | build(4, 4) | 4 | 7 | 4 | empty | empty |
| End | 5 | tree [3,9,20,null,null,15,7] |
Every empty range returns None at if lo > hi without using a preorder value. At step 3, pre_idx is 2 because step 2, the one-node left subtree, used exactly one value. Had build(2, 4) run before build(0, 0), it would have taken preorder[1] = 9 as the right subtree's root, and 9 is not even in inorder[2..4].
preorder = [3,9,20,15,7], inorder = [9,3,15,20,7][3,9,20,null,null,15,7]Example 1, preorder = [3,9,20,15,7], inorder = [9,3,15,20,7], so where = {9: 0, 3: 1, 15: 2, 20: 3, 7: 4}. Each row is one build(lo, hi) that makes a node, in the order the calls run:
| Step | Call | pre_idx | root | mid | Left range | Right range |
|---|---|---|---|---|---|---|
| 1 | build(0, 4) | 0 | 3 | 1 | inorder[0..0] = [9] | inorder[2..4] = [15, 20, 7] |
| 2 | build(0, 0) | 1 | 9 | 0 | empty | empty |
| 3 | build(2, 4) | 2 | 20 | 3 | inorder[2..2] = [15] | inorder[4..4] = [7] |
| 4 | build(2, 2) | 3 | 15 | 2 | empty | empty |
| 5 | build(4, 4) | 4 | 7 | 4 | empty | empty |
| End | 5 | tree [3,9,20,null,null,15,7] |
Every empty range returns None at if lo > hi without using a preorder value. At step 3, pre_idx is 2 because step 2, the one-node left subtree, used exactly one value. Had build(2, 4) run before build(0, 0), it would have taken preorder[1] = 9 as the right subtree's root, and 9 is not even in inorder[2..4].
| 1 | Preorder names the roots and inorder splits them: `preorder[pre_idx]` is the root of the subtree you build next, and its place in `inorder` separates its left subtree from its right one. |
| 2 | `build(lo, hi)` builds the values in `inorder[lo..hi]`: take `root = TreeNode(preorder[pre_idx])`, move `pre_idx` on, then `mid = where[root.val]` splits the range. `where` maps each value to its inorder index, built once. |
| 3 | The shape: `if lo > hi: return None`; make `root`; `pre_idx += 1`; `mid = where[root.val]`; `root.left = build(lo, mid - 1)`; `root.right = build(mid + 1, hi)`; `return root`. Start with `build(0, len(inorder) - 1)`. |
| 4 | The trap: `root.left = build(lo, mid - 1)` must run before `root.right = build(mid + 1, hi)`. Preorder lists the whole left subtree first, so on `preorder = [3,9,20,15,7]` building the right side first gives 9 to the right subtree. |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
One traversal can't pin down a tree: [1, 2] in preorder is 1 with a left child 2 or 1 with a right child 2. Two traversals can, when the values are distinct, because they carry different facts. Preorder names the roots: every subtree starts with its root. Inorder gives the split: a root sits between everything in its left subtree and everything in its right subtree. So take the next root from preorder, find it in inorder, and build each side from its own part of the range. That is Construct Binary Tree: Bottom-Up DFS that builds instead of measuring, with a hash map for the lookup.
🏢 The Analogy: An Org Chart From Two Lists
You get two lists of the same company's staff. The first is a phone tree: every manager is called before anyone in their team, and the first half of each team is called before the second half. The second is a seating plan: each manager sits between the first half of their team and the second half. The next name not yet used on the phone tree is the manager of the group you are placing. Find that name on the seating plan, and the people to the left of it are one half of the team and those to the right the other.
🔑 Why It Works
build(lo, hi) uses exactly one preorder value for every node in inorder[lo..hi], so when the left call returns, pre_idx has just moved past the whole left subtree and points at the right subtree's root. The trap sits on the two calls: the left one must come first, because preorder lists the left subtree before the right one.
Building the right subtree before the left one
Passing
pre_idxdown as an argumentCalling
inorder.index(root.val)in every callWriting
lo >= hias the empty test
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"values are all different", "walked twice" (once into preorder, once into inorder) and "rebuild that tree": two traversal orders of one tree plus distinct values is the signal for Construct Binary Tree. Preorder will name each root, and the distinct values let inorder split around it at one exact index.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
build(lo, hi) builds exactly the values in inorder[lo..hi], and when it starts, preorder[pre_idx] is the root of that range. It makes root = TreeNode(preorder[pre_idx]), moves pre_idx on, finds mid = where[root.val], and builds inorder[lo..mid-1] as the left subtree and inorder[mid+1..hi] as the right one. The answer is build(0, len(inorder) - 1).
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
The card's trap: build the left range before the right one, because
pre_idxhands out roots in preorder.Don't slice the lists (
buildTree(preorder[1:mid + 1], inorder[:mid])): it gives the right tree, but every call copies its whole range, O(N^2) on a chain of 3000 nodes. Index ranges and one sharedpre_idxcopy nothing.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd use Construct Binary Tree. Preorder always lists a root before the rest of its subtree, so the next unused preorder value is the root of whatever I'm building. Inorder puts that root between its left and right subtrees, so its index there splits the range. I build a map from each value to its inorder index once, keep one shared cursor, pre_idx, into preorder, and write build(lo, hi) for the values of inorder from lo to hi. An empty range gives None; otherwise I take the next preorder value as the root, look up its index, and build the left range, then the right range. The trap is that order: preorder lists the whole left subtree before the right one, so building the right side first would steal the left subtree's root. Each node is created once with an
O(1)lookup, so it'sO(N)time, withO(N)for the map and O(H) for the recursion stack.
Complexity & Mathematical Proof
O(N)
Building where walks inorder once: N steps. Then every call of build either returns None at once or creates one node, and each node is created exactly once because pre_idx only moves forward. A tree of N nodes has N + 1 empty child slots, so there are 2N + 1 calls. A call that creates a node does O(1) work: one TreeNode, one pre_idx += 1, one dictionary lookup where[root.val], two calls. Total: N + (2N + 1) · O(1) = O(N).
O(N) index map + O(H) recursion stack
where holds one entry per value: O(N). The recursion goes one level deeper per tree level, so the call stack holds at most H + 1 frames, where H is the tree's height: about log N when balanced, N on a chain. The returned tree has N nodes; that is the output, counted apart from the extra space.
Derivation Progression
N
where = {val: i for i, val in enumerate(inorder)} visits each value once.
N + (N + 1) = 2N + 1
One call per node (it creates the node) and one per empty child slot (if lo > hi: return None).
O(1)
TreeNode(preorder[pre_idx]), pre_idx += 1 and mid = where[root.val]: no scan of the range.
O(N)
N for the map plus 2N + 1 calls of O(1) each.
Variable Definitions
Number of nodes: the length of preorder and of inorder
Height of the tree: about log N when balanced, up to N on a chain
Memory Architecture & Bounds
O(H): one frame per level of the current root-to-node path
O(N): where has one entry per value
O(N): the N nodes of the returned tree (the output, not extra space)
Boundary Best / Worst Cases
time and an stack on a balanced tree
time; the stack depth is the tree height
time and an stack on a chain
Graph & Tree Traversal Frontier
Senior SWE Deconstruction & Hardware Caveats
Triggers: "walked twice", "values are all different", "rebuild that tree". Two traversal orders of one tree: preorder names each root, and distinct values let inorder split around it at one exact index: Construct Binary Tree.
distinct values in . Searching inorder for every root costs up to steps each, about on a chain; a value-to-index map makes each split , so the build is time with an map and an recursion stack.
A chain of 3000 nodes is 3000 calls deep, past the default recursion limit of many runtimes (CPython's is 1000): raise the limit, or build with an explicit stack that pushes each preorder value and pops while its top equals the next inorder value. With repeated values, where keeps one index per value and the split becomes ambiguous: two traversals no longer fix the tree, which is why real serializers write a marker for every missing child or give each node an id.
Construct Binary Tree from Preorder and Inorder Traversal (LeetCode 105)
A binary tree whose values are all different was walked twice, and each walk wrote its values into a list.
preorderlists every subtree as its root first, then its left subtree, then its right subtree.inorderlists every subtree as its left subtree first, then its root, then its right subtree.
Both lists describe the same tree and hold the same values. Rebuild that tree and return its root.
Worked Examples
preorder = [3,9,20,15,7], inorder = [9,3,15,20,7][3,9,20,null,null,15,7]preorder = [-1], inorder = [-1][-1]⚖️Formal Constraints & Bounds
1 <= preorder.length <= 3000inorder.length == preorder.length-3000 <= preorder[i], inorder[i] <= 3000The values in
preorderare distinct, and so are the values ininorder.Every value of
inorderalso appears inpreorder.preorderis the tree's preorder traversal andinorderis the same tree's inorder traversal.
Core Insight
Preorder gives each subtree's root before anything else in it, and inorder puts that root between its two subtrees. So the next unused preorder value is the root, its inorder index splits the range, and building the left side first keeps the preorder cursor on the right root for the right side.
Real-World Scenario & Production Applications
Tree-shaped data is often stored as a flat list and read back later: a listing of folders written parent-first is a preorder, and so is the order in which many serializers write an object tree. One order alone can't give back the shape; a second order, or a marker for every missing child, can. Restoring a saved tree from such listings is this problem.
Step-by-Step Execution Trace Table
Example 1, preorder = [3,9,20,15,7], inorder = [9,3,15,20,7], so where = {9: 0, 3: 1, 15: 2, 20: 3, 7: 4}. Each row is one build(lo, hi) that makes a node, in the order the calls run:
| Step | Call | pre_idx | root | mid | Left range | Right range |
|---|---|---|---|---|---|---|
| 1 | build(0, 4) | 0 | 3 | 1 | inorder[0..0] = [9] | inorder[2..4] = [15, 20, 7] |
| 2 | build(0, 0) | 1 | 9 | 0 | empty | empty |
| 3 | build(2, 4) | 2 | 20 | 3 | inorder[2..2] = [15] | inorder[4..4] = [7] |
| 4 | build(2, 2) | 3 | 15 | 2 | empty | empty |
| 5 | build(4, 4) | 4 | 7 | 4 | empty | empty |
| End | 5 | tree [3,9,20,null,null,15,7] |
Every empty range returns None at if lo > hi without using a preorder value. At step 3, pre_idx is 2 because step 2, the one-node left subtree, used exactly one value. Had build(2, 4) run before build(0, 0), it would have taken preorder[1] = 9 as the right subtree's root, and 9 is not even in inorder[2..4].
preorder = [3,9,20,15,7], inorder = [9,3,15,20,7][3,9,20,null,null,15,7]Example 1, preorder = [3,9,20,15,7], inorder = [9,3,15,20,7], so where = {9: 0, 3: 1, 15: 2, 20: 3, 7: 4}. Each row is one build(lo, hi) that makes a node, in the order the calls run:
| Step | Call | pre_idx | root | mid | Left range | Right range |
|---|---|---|---|---|---|---|
| 1 | build(0, 4) | 0 | 3 | 1 | inorder[0..0] = [9] | inorder[2..4] = [15, 20, 7] |
| 2 | build(0, 0) | 1 | 9 | 0 | empty | empty |
| 3 | build(2, 4) | 2 | 20 | 3 | inorder[2..2] = [15] | inorder[4..4] = [7] |
| 4 | build(2, 2) | 3 | 15 | 2 | empty | empty |
| 5 | build(4, 4) | 4 | 7 | 4 | empty | empty |
| End | 5 | tree [3,9,20,null,null,15,7] |
Every empty range returns None at if lo > hi without using a preorder value. At step 3, pre_idx is 2 because step 2, the one-node left subtree, used exactly one value. Had build(2, 4) run before build(0, 0), it would have taken preorder[1] = 9 as the right subtree's root, and 9 is not even in inorder[2..4].
| 1 | Preorder names the roots and inorder splits them: `preorder[pre_idx]` is the root of the subtree you build next, and its place in `inorder` separates its left subtree from its right one. |
| 2 | `build(lo, hi)` builds the values in `inorder[lo..hi]`: take `root = TreeNode(preorder[pre_idx])`, move `pre_idx` on, then `mid = where[root.val]` splits the range. `where` maps each value to its inorder index, built once. |
| 3 | The shape: `if lo > hi: return None`; make `root`; `pre_idx += 1`; `mid = where[root.val]`; `root.left = build(lo, mid - 1)`; `root.right = build(mid + 1, hi)`; `return root`. Start with `build(0, len(inorder) - 1)`. |
| 4 | The trap: `root.left = build(lo, mid - 1)` must run before `root.right = build(mid + 1, hi)`. Preorder lists the whole left subtree first, so on `preorder = [3,9,20,15,7]` building the right side first gives 9 to the right subtree. |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
One traversal can't pin down a tree: [1, 2] in preorder is 1 with a left child 2 or 1 with a right child 2. Two traversals can, when the values are distinct, because they carry different facts. Preorder names the roots: every subtree starts with its root. Inorder gives the split: a root sits between everything in its left subtree and everything in its right subtree. So take the next root from preorder, find it in inorder, and build each side from its own part of the range. That is Construct Binary Tree: Bottom-Up DFS that builds instead of measuring, with a hash map for the lookup.
🏢 The Analogy: An Org Chart From Two Lists
You get two lists of the same company's staff. The first is a phone tree: every manager is called before anyone in their team, and the first half of each team is called before the second half. The second is a seating plan: each manager sits between the first half of their team and the second half. The next name not yet used on the phone tree is the manager of the group you are placing. Find that name on the seating plan, and the people to the left of it are one half of the team and those to the right the other.
🔑 Why It Works
build(lo, hi) uses exactly one preorder value for every node in inorder[lo..hi], so when the left call returns, pre_idx has just moved past the whole left subtree and points at the right subtree's root. The trap sits on the two calls: the left one must come first, because preorder lists the left subtree before the right one.
Building the right subtree before the left one
Passing
pre_idxdown as an argumentCalling
inorder.index(root.val)in every callWriting
lo >= hias the empty test
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"values are all different", "walked twice" (once into preorder, once into inorder) and "rebuild that tree": two traversal orders of one tree plus distinct values is the signal for Construct Binary Tree. Preorder will name each root, and the distinct values let inorder split around it at one exact index.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
build(lo, hi) builds exactly the values in inorder[lo..hi], and when it starts, preorder[pre_idx] is the root of that range. It makes root = TreeNode(preorder[pre_idx]), moves pre_idx on, finds mid = where[root.val], and builds inorder[lo..mid-1] as the left subtree and inorder[mid+1..hi] as the right one. The answer is build(0, len(inorder) - 1).
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
The card's trap: build the left range before the right one, because
pre_idxhands out roots in preorder.Don't slice the lists (
buildTree(preorder[1:mid + 1], inorder[:mid])): it gives the right tree, but every call copies its whole range, O(N^2) on a chain of 3000 nodes. Index ranges and one sharedpre_idxcopy nothing.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd use Construct Binary Tree. Preorder always lists a root before the rest of its subtree, so the next unused preorder value is the root of whatever I'm building. Inorder puts that root between its left and right subtrees, so its index there splits the range. I build a map from each value to its inorder index once, keep one shared cursor, pre_idx, into preorder, and write build(lo, hi) for the values of inorder from lo to hi. An empty range gives None; otherwise I take the next preorder value as the root, look up its index, and build the left range, then the right range. The trap is that order: preorder lists the whole left subtree before the right one, so building the right side first would steal the left subtree's root. Each node is created once with an
O(1)lookup, so it'sO(N)time, withO(N)for the map and O(H) for the recursion stack.
Complexity & Mathematical Proof
O(N)
Building where walks inorder once: N steps. Then every call of build either returns None at once or creates one node, and each node is created exactly once because pre_idx only moves forward. A tree of N nodes has N + 1 empty child slots, so there are 2N + 1 calls. A call that creates a node does O(1) work: one TreeNode, one pre_idx += 1, one dictionary lookup where[root.val], two calls. Total: N + (2N + 1) · O(1) = O(N).
O(N) index map + O(H) recursion stack
where holds one entry per value: O(N). The recursion goes one level deeper per tree level, so the call stack holds at most H + 1 frames, where H is the tree's height: about log N when balanced, N on a chain. The returned tree has N nodes; that is the output, counted apart from the extra space.
Derivation Progression
N
where = {val: i for i, val in enumerate(inorder)} visits each value once.
N + (N + 1) = 2N + 1
One call per node (it creates the node) and one per empty child slot (if lo > hi: return None).
O(1)
TreeNode(preorder[pre_idx]), pre_idx += 1 and mid = where[root.val]: no scan of the range.
O(N)
N for the map plus 2N + 1 calls of O(1) each.
Variable Definitions
Number of nodes: the length of preorder and of inorder
Height of the tree: about log N when balanced, up to N on a chain
Memory Architecture & Bounds
O(H): one frame per level of the current root-to-node path
O(N): where has one entry per value
O(N): the N nodes of the returned tree (the output, not extra space)
Boundary Best / Worst Cases
time and an stack on a balanced tree
time; the stack depth is the tree height
time and an stack on a chain
Graph & Tree Traversal Frontier
Senior SWE Deconstruction & Hardware Caveats
Triggers: "walked twice", "values are all different", "rebuild that tree". Two traversal orders of one tree: preorder names each root, and distinct values let inorder split around it at one exact index: Construct Binary Tree.
distinct values in . Searching inorder for every root costs up to steps each, about on a chain; a value-to-index map makes each split , so the build is time with an map and an recursion stack.
A chain of 3000 nodes is 3000 calls deep, past the default recursion limit of many runtimes (CPython's is 1000): raise the limit, or build with an explicit stack that pushes each preorder value and pops while its top equals the next inorder value. With repeated values, where keeps one index per value and the split becomes ambiguous: two traversals no longer fix the tree, which is why real serializers write a marker for every missing child or give each node an id.