What is the pricing and subscription model for Hi👋SpeedAlgo?

The entire core curriculum of 12 patterns and 187 archetypes is 100% free to access with no credit card required. Students receive 40 free compute coins upon registration, +20 daily login coins, and +25 referral coins. A 24-hour unlimited AI coaching pass costs only 5 coins. Alternatively, developers can use Bring-Your-Own-Key (BYOK) for completely free unlimited AI coaching with personal Gemini or OpenAI keys. There are no recurring subscription fees.

What is the refund and cancellation policy?

Hi👋SpeedAlgo has zero recurring subscriptions, zero automatic renewals, and zero hidden billing traps. Because the core platform and learning materials are free, students never face unwanted credit card charges or recurring payment obligations.

Who creates and maintains the curriculum?

Hi👋SpeedAlgo is developed and maintained by Hi👋WebEnterprise (https://hiwebenterprise.com), an engineering organization focused on developer education, deliberate practice methodologies, and cognitive ergonomics for technical interviews.

How does Hi👋SpeedAlgo prepare candidates for senior and staff SWE interviews?

Rather than rote LeetCode grinding, Hi👋SpeedAlgo enforces deliberate practice: proving invariants, articulating Big-O tradeoffs, managing edge cases, and defending algorithmic approaches to a Senior SWE AI Mock Coach in an integrated Monaco code editor.

18. Tree Construction: Construct Binary Tree from Preorder and Inorder Traversal (LC 105) • Invariant Proof & Speed-Run

Theory Context•Depth-First Search (DFS)

MediumLC 105

Construct Binary Tree from Preorder and Inorder Traversal (LeetCode 105)

You will see how preorder names every root and inorder splits every range, so each node is built once with one lookup.

Target Frequency:AmazonMicrosoftBloomberg

A binary tree whose values are all different was walked twice, and each walk wrote its values into a list.

preorder lists every subtree as its root first, then its left subtree, then its right subtree.
inorder lists 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

Example 1

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

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

Explanation: 3 comes first in preorder, so it is the root. In inorder, only 9 sits left of 3, so 9 is the whole left subtree; 15, 20 and 7 sit right of it. Of those, 20 comes first in preorder, so it roots the right side, with 15 on its left and 7 on its right.

Example 2

Input:preorder = [-1], inorder = [-1]

Output:[-1]

Explanation: One value makes a tree of one node.

⚖️Formal Constraints & Bounds

1 <= preorder.length <= 3000
inorder.length == preorder.length
-3000 <= preorder[i], inorder[i] <= 3000
The values in preorder are distinct, and so are the values in inorder.
Every value of inorder also appears in preorder.
preorder is the tree's preorder traversal and inorder is the same tree's inorder traversal.

Deep-Dive & Conceptual Insights

Why It Works & Core Invariant

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]`

Scroll horizontally to see all columns, or expand to full screen

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].

Trace Inputpreorder = [3,9,20,15,7], inorder = [9,3,15,20,7]

Expected[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]`

Scroll horizontally to see all columns, or expand to full screen

Core Invariant Specification & Code Shape

Archetype Code Shape

Python

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.

Target: Construct Binary Tree from Preorder and Inorder Traversal (LeetCode 105). Values are distinct, so each one has exactly one index; building the map once saves a search per node.

Boundary Model: Depth-First Recursion / Call Stack Frame Lifecycle

Subtree bottom-up aggregation: a node combines child subtree solutions upon backtrack; top-down invariants pass accumulated state down the path.

Loop Invariant Termination

Base case: if not node: return base; recursive calls on left/right child nodes.

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.

🪄 The Mathematical Harmony / Magic Trick

Code / Blueprint

where = {val: i for i, val in enumerate(inorder)}
pre_idx = 0
 
def build(lo, hi):
    nonlocal pre_idx
    if lo > hi:
        return None
    root = TreeNode(preorder[pre_idx])
    pre_idx += 1
    mid = where[root.val]
    root.left = build(lo, mid - 1)
    root.right = build(mid + 1, hi)
    return root
 
return build(0, len(inorder) - 1)

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.

💡 Summary

Take preorder[pre_idx] as the root, split inorder[lo..hi] at mid = where[root.val], and build the left subtree before the right one. Every node is created once with an O(1) lookup: $O(N)$ time, an $O(N)$ index map and an $O(H)$ recursion stack.

Building the right subtree first: root.left = build(lo, mid - 1) comes before root.right = build(mid + 1, hi). pre_idx hands out roots in preorder, so on preorder = [3,9,20,15,7] the right call would take 9 as its root.
Passing the cursor down instead of sharing it: pre_idx is one counter for every call (nonlocal). Passed as an argument, the right call starts right after its parent, as if the left subtree were empty.
Searching inorder in every call: inorder.index(root.val) rescans the range, O(N^2) on a chain; build where once for O(1) lookups.
Treating one value as empty: the empty test is lo > hi. With lo >= hi, a range of one value, a leaf, returns None without using its preorder value, so later roots shift (LeetCode's Example 1 comes back as [3,null,9,null,20,15]).

Senior SWE Reasoning Architecture

4-Phase Thought Process Model

You will see how a senior engineer reads two traversals of one tree as roots plus splits, and rebuilds it in one pass.

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

root.left = build(lo, mid - 1) comes before root.right = build(mid + 1, hi): pre_idx hands out roots in preorder, so on preorder = [3,9,20,15,7] building the right side first gives 9 to the right subtree.
pre_idx is one counter shared by every call (nonlocal): passed down as an argument, the right call starts right after its parent, as if the left subtree were empty.
Build where once: inorder.index(root.val) in every call rescans the range, O(N^2) on a chain of 3000 nodes.
The empty test is lo > hi, not lo >= hi: lo == hi is a range of one value, a leaf, and with >= every leaf is skipped without using its preorder value, so later roots shift (LeetCode's Example 1 comes back as [3,null,9,null,20,15]).

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's O(N) time, with O(N) for the map and O(H) for the recursion stack.

So: preorder[pre_idx] is the root, mid = where[root.val] splits inorder[lo..hi], and the left call runs before the right one.

Big-O Invariant Derivation

Complexity & Mathematical Proof

TIME COMPLEXITY

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).

SPACE COMPLEXITY

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.

Formal Recurrence Relation

$T(N) = N + (2N + 1) \cdot O(1) = O(N)$

Derivation Progression

Index map

N

where = {val: i for i, val in enumerate(inorder)} visits each value once.

Calls

N + (N + 1) = 2N + 1

One call per node (it creates the node) and one per empty child slot (if lo > hi: return None).

Work per call

O(1)

TreeNode(preorder[pre_idx]), pre_idx += 1 and mid = where[root.val]: no scan of the range.

Total

O(N)

N for the map plus 2N + 1 calls of O(1) each.

Variable Definitions

$N$

Number of nodes: the length of preorder and of inorder

$H$

Height of the tree: about log N when balanced, up to N on a chain

Memory Architecture & Bounds

🟣 Call Stack

O(H): one frame per level of the current root-to-node path

🔵 Auxiliary Heap

O(N): where has one entry per value

🟢 Output Space

O(N): the N nodes of the returned tree (the output, not extra space)

Boundary Best / Worst Cases

Best Case

$O(N)$ time and an $O(\log N)$ stack on a balanced tree

Average Case

$O(N)$ time; the stack depth is the tree height

Worst Case

$O(N)$ time and an $O(N)$ stack on a chain

Graph & Tree Traversal Frontier

Synthesizing vector architecture diagram...

Staff+ Engineering Perspective

Senior SWE Deconstruction & Hardware Caveats

ARCHITECTURAL SIGNALS & INTERVIEW TRIGGERS

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.

CONSTRAINTS & BOUNDS

$1 \le N \le 3000$ distinct values in $[-3000, 3000]$ . Searching inorder for every root costs up to $N$ steps each, about $4.5 \times 10^6$ on a chain; a value-to-index map makes each split $O(1)$ , so the build is $O(N)$ time with an $O(N)$ map and an $O(H)$ recursion stack.

FAANG PRODUCTION TRAPS & EDGE CASES

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.

Core Algorithmic State Invariants

1. Preorder Names the Root

`preorder[pre_idx]` is the root of the subtree `build(lo, hi)` is making: preorder lists every root before the rest of its subtree, and `pre_idx` only moves forward.

2. Left Before Right

`root.left = build(lo, mid - 1)` runs before `root.right = build(mid + 1, hi)`: the left call uses one preorder value per node of `inorder[lo..mid-1]`, which leaves `pre_idx` on the right subtree's root.

3. One Lookup per Node

`where` maps each value to its inorder index once, so `mid = where[root.val]` is O(1): O(N) time, an O(N) map and an O(H) recursion stack.

Theory Context•Depth-First Search (DFS)

MediumLC 105

Construct Binary Tree from Preorder and Inorder Traversal (LeetCode 105)

You will see how preorder names every root and inorder splits every range, so each node is built once with one lookup.

Target Frequency:AmazonMicrosoftBloomberg

A binary tree whose values are all different was walked twice, and each walk wrote its values into a list.

preorder lists every subtree as its root first, then its left subtree, then its right subtree.
inorder lists 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

Example 1

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

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

Example 2

Input:preorder = [-1], inorder = [-1]

Output:[-1]

Explanation: One value makes a tree of one node.

⚖️Formal Constraints & Bounds

1 <= preorder.length <= 3000
inorder.length == preorder.length
-3000 <= preorder[i], inorder[i] <= 3000
The values in preorder are distinct, and so are the values in inorder.
Every value of inorder also appears in preorder.
preorder is the tree's preorder traversal and inorder is the same tree's inorder traversal.

Deep-Dive & Conceptual Insights

Why It Works & Core Invariant

Real-World Scenario & Production Applications

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]`

Scroll horizontally to see all columns, or expand to full screen

Trace Inputpreorder = [3,9,20,15,7], inorder = [9,3,15,20,7]

Expected[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]`

Scroll horizontally to see all columns, or expand to full screen

Core Invariant Specification & Code Shape

Archetype Code Shape

Python

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.

Target: Construct Binary Tree from Preorder and Inorder Traversal (LeetCode 105). Values are distinct, so each one has exactly one index; building the map once saves a search per node.

Boundary Model: Depth-First Recursion / Call Stack Frame Lifecycle

Subtree bottom-up aggregation: a node combines child subtree solutions upon backtrack; top-down invariants pass accumulated state down the path.

Loop Invariant Termination

Base case: if not node: return base; recursive calls on left/right child nodes.

Conceptual Narrative

🧭 Conceptual Foundation & Pattern Intuition

🏢 The Analogy: An Org Chart From Two Lists

🪄 The Mathematical Harmony / Magic Trick

Code / Blueprint

where = {val: i for i, val in enumerate(inorder)}
pre_idx = 0
 
def build(lo, hi):
    nonlocal pre_idx
    if lo > hi:
        return None
    root = TreeNode(preorder[pre_idx])
    pre_idx += 1
    mid = where[root.val]
    root.left = build(lo, mid - 1)
    root.right = build(mid + 1, hi)
    return root
 
return build(0, len(inorder) - 1)

💡 Summary

Building the right subtree first: root.left = build(lo, mid - 1) comes before root.right = build(mid + 1, hi). pre_idx hands out roots in preorder, so on preorder = [3,9,20,15,7] the right call would take 9 as its root.
Passing the cursor down instead of sharing it: pre_idx is one counter for every call (nonlocal). Passed as an argument, the right call starts right after its parent, as if the left subtree were empty.
Searching inorder in every call: inorder.index(root.val) rescans the range, O(N^2) on a chain; build where once for O(1) lookups.
Treating one value as empty: the empty test is lo > hi. With lo >= hi, a range of one value, a leaf, returns None without using its preorder value, so later roots shift (LeetCode's Example 1 comes back as [3,null,9,null,20,15]).

Senior SWE Reasoning Architecture

4-Phase Thought Process Model

You will see how a senior engineer reads two traversals of one tree as roots plus splits, and rebuilds it in one pass.

Pattern Recognition Signals

The 10-second spot

Formulating the Predicate & Invariants

Turning intuition into a boolean rule

Silent Failure Traps & Edge Cases

Where confident candidates still lose points

root.left = build(lo, mid - 1) comes before root.right = build(mid + 1, hi): pre_idx hands out roots in preorder, so on preorder = [3,9,20,15,7] building the right side first gives 9 to the right subtree.
pre_idx is one counter shared by every call (nonlocal): passed down as an argument, the right call starts right after its parent, as if the left subtree were empty.
Build where once: inorder.index(root.val) in every call rescans the range, O(N^2) on a chain of 3000 nodes.
The empty test is lo > hi, not lo >= hi: lo == hi is a range of one value, a leaf, and with >= every leaf is skipped without using its preorder value, so later roots shift (LeetCode's Example 1 comes back as [3,null,9,null,20,15]).

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's O(N) time, with O(N) for the map and O(H) for the recursion stack.

So: preorder[pre_idx] is the root, mid = where[root.val] splits inorder[lo..hi], and the left call runs before the right one.

Big-O Invariant Derivation

Complexity & Mathematical Proof

TIME COMPLEXITY

O(N)

SPACE COMPLEXITY

O(N) index map + O(H) recursion stack

Formal Recurrence Relation

$T(N) = N + (2N + 1) \cdot O(1) = O(N)$

Derivation Progression

Index map

N

where = {val: i for i, val in enumerate(inorder)} visits each value once.

Calls

N + (N + 1) = 2N + 1

One call per node (it creates the node) and one per empty child slot (if lo > hi: return None).

Work per call

O(1)

TreeNode(preorder[pre_idx]), pre_idx += 1 and mid = where[root.val]: no scan of the range.

Total

O(N)

N for the map plus 2N + 1 calls of O(1) each.

Variable Definitions

$N$

Number of nodes: the length of preorder and of inorder

$H$

Height of the tree: about log N when balanced, up to N on a chain

Memory Architecture & Bounds

🟣 Call Stack

O(H): one frame per level of the current root-to-node path

🔵 Auxiliary Heap

O(N): where has one entry per value

🟢 Output Space

O(N): the N nodes of the returned tree (the output, not extra space)

Boundary Best / Worst Cases

Best Case

$O(N)$ time and an $O(\log N)$ stack on a balanced tree

Average Case

$O(N)$ time; the stack depth is the tree height

Worst Case

$O(N)$ time and an $O(N)$ stack on a chain

Graph & Tree Traversal Frontier

Synthesizing vector architecture diagram...

Staff+ Engineering Perspective

Senior SWE Deconstruction & Hardware Caveats

ARCHITECTURAL SIGNALS & INTERVIEW TRIGGERS

CONSTRAINTS & BOUNDS

FAANG PRODUCTION TRAPS & EDGE CASES

Core Algorithmic State Invariants

1. Preorder Names the Root

`preorder[pre_idx]` is the root of the subtree `build(lo, hi)` is making: preorder lists every root before the rest of its subtree, and `pre_idx` only moves forward.

2. Left Before Right

3. One Lookup per Node

`where` maps each value to its inorder index once, so `mid = where[root.val]` is O(1): O(N) time, an O(N) map and an O(H) recursion stack.

Rosetta Dual-Monaco Comparison

Python 3

CANONICAL INVARIANT TEMPLATE

CONCRETE: CONSTRUCT BINARY TREE FROM PREORDER AND INORDER TRAVERSAL (LEETCODE 105)

T = O(N)S = O(N) index map + O(H) recursion stack

Pattern Implementation Mapping TableCanonical Invariant ⟷ Concrete Code ⟷ Engineering Rationale

Canonical Invariant	Concrete Code	Engineering Rationale
Find any value in inorder in O(1)	`where = {val: i for i, val in enumerate(inorder)}`	Values are distinct, so each one has exactly one index; building the map once saves a search per node.
One cursor over preorder, shared by every call	`pre_idx = 0`	`preorder[pre_idx]` is always the root of the next subtree to build; `nonlocal pre_idx` lets every call move the same cursor.
Empty range	`if lo > hi: return None`	`lo == hi` is one node, a leaf; only `lo > hi` means no subtree.
Take the next root from preorder	`root = TreeNode(preorder[pre_idx]) pre_idx += 1`	Preorder lists every subtree's root before anything else in that subtree.
Split the range at the root	`mid = where[root.val]`	Inorder puts the root between its subtrees: `inorder[lo..mid-1]` is the left one, `inorder[mid+1..hi]` the right one.
Left subtree first (the trap)	`root.left = build(lo, mid - 1) root.right = build(mid + 1, hi)`	Preorder lists the whole left subtree before the right one, so the left call must use up its roots first.
The whole tree	`return build(0, len(inorder) - 1)`	The full inorder range is the whole tree, and `preorder[0]` is its root.

Step

Call

pre_idx

root

mid

Left range

Right range

build(0, 4)

inorder[0..0] = [9]

inorder[2..4] = [15, 20, 7]

build(0, 0)

empty

build(2, 4)

inorder[2..2] = [15]

inorder[4..4] = [7]

build(2, 2)

empty

build(4, 4)

empty

End

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

Step

Call

pre_idx

root

mid

Left range

Right range

build(0, 4)

inorder[0..0] = [9]

inorder[2..4] = [15, 20, 7]

build(0, 0)

empty

build(2, 4)

inorder[2..2] = [15]

inorder[4..4] = [7]

build(2, 2)

empty

build(4, 4)

empty

End

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

where = {val: i for i, val in enumerate(inorder)} pre_idx = 0 def build(lo, hi): nonlocal pre_idx if lo > hi: return None root = TreeNode(preorder[pre_idx]) pre_idx += 1 mid = where[root.val] root.left = build(lo, mid - 1) root.right = build(mid + 1, hi) return root return build(0, len(inorder) - 1)

Step

Call

pre_idx

root

mid

Left range

Right range

build(0, 4)

inorder[0..0] = [9]

inorder[2..4] = [15, 20, 7]

build(0, 0)

empty

build(2, 4)

inorder[2..2] = [15]

inorder[4..4] = [7]

build(2, 2)

empty

build(4, 4)

empty

End

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

Step

Call

pre_idx

root

mid

Left range

Right range

build(0, 4)

inorder[0..0] = [9]

inorder[2..4] = [15, 20, 7]

build(0, 0)

empty

build(2, 4)

inorder[2..2] = [15]

inorder[4..4] = [7]

build(2, 2)

empty

build(4, 4)

empty

End

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

Canonical Invariant

Concrete Code

Engineering Rationale

Find any value in inorder in O(1)

where = {val: i for i, val in enumerate(inorder)}

Values are distinct, so each one has exactly one index; building the map once saves a search per node.

One cursor over preorder, shared by every call

pre_idx = 0

`preorder[pre_idx]` is always the root of the next subtree to build; `nonlocal pre_idx` lets every call move the same cursor.

Empty range

if lo > hi:
    return None

`lo == hi` is one node, a leaf; only `lo > hi` means no subtree.

Take the next root from preorder

root = TreeNode(preorder[pre_idx])
pre_idx += 1

Preorder lists every subtree's root before anything else in that subtree.

Split the range at the root

mid = where[root.val]

Inorder puts the root between its subtrees: `inorder[lo..mid-1]` is the left one, `inorder[mid+1..hi]` the right one.

Left subtree first (the trap)

root.left = build(lo, mid - 1)
root.right = build(mid + 1, hi)

Preorder lists the whole left subtree before the right one, so the left call must use up its roots first.

The whole tree

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

The full inorder range is the whole tree, and `preorder[0]` is its root.