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

The entire core curriculum of 12 patterns and 180 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.

16. BST Inorder Sorted Stream: Kth Smallest Element in a BST (LC 230) • Invariant Proof & Speed-Run

Theory Context•Depth-First Search (DFS)

MediumLC 230

Kth Smallest Element in a BST (LeetCode 230)

You will see how an inorder walk reads a BST as a sorted list and stops at the k-th value.

Target Frequency:AmazonMetaGoogle

You get the root of a binary search tree and a whole number k. Imagine writing every value in the tree in a row, smallest first, and numbering the positions from 1: return the value that lands in position k.

In a binary search tree, the values in a node's left subtree are smaller than the node's value, and the values in its right subtree are larger.

Follow-up: if nodes are inserted and deleted often and this question is asked again and again, how would you make each answer faster?

Worked Examples

Example 1

Input:root = [3,1,4,null,2], k = 1

Output:1

Explanation: Written smallest first, the values are `1, 2, 3, 4`. Position 1 holds `1`, a leaf on the left, even though `3` sits at the top of the tree.

Example 2

Input:root = [5,3,6,2,4,null,null,1], k = 3

Output:3

Explanation: Written smallest first, the values are `1, 2, 3, 4, 5, 6`, so position 3 holds `3`.

⚖️Formal Constraints & Bounds

The number of nodes in the tree is n.
1 <= k <= n <= 10⁴
0 <= Node.val <= 10⁴

Deep-Dive & Conceptual Insights

Why It Works & Core Invariant

Rank in a BST is position in sorted order, and the inorder walk produces sorted order one value per visit, so the k-th visit is the answer and the walk can stop there.

Real-World Scenario & Production Applications

Rank queries on ordered data are everywhere: the 10th cheapest listing, the median of a set of latency samples, the k-th oldest open ticket. When the data already sits in a search tree it is sorted in place, so walking it in order and stopping at the k-th item beats copying everything out and sorting it again.

Step-by-Step Execution Trace Table

Example 2, root = [5,3,6,2,4,null,null,1], k = 3:

Step	What runs	`stack` (bottom to top)	`node`	`k`	What it means
1	Dive: `stack.append(node)`, `node = node.left`	`[5, 3, 2, 1]`	`None`	3	Four nodes pushed, none counted: pushing is not visiting
2	`node = stack.pop()`, `k -= 1`	`[5, 3, 2]`	1	2	1st visit: 1 is the smallest value
3	`node = node.right` is `None`; pop, `k -= 1`	`[5, 3]`	2	1	2nd visit
4	`node = node.right` is `None`; pop, `k -= 1`	`[5]`	3	0	3rd visit: `k == 0`, return 3

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

Counting pushes instead would reach k == 0 at the third push, node 2, and return the wrong value.

Trace Inputroot = [3,1,4,null,2], k = 1

Expected1

Example 2, root = [5,3,6,2,4,null,null,1], k = 3:

Step	What runs	`stack` (bottom to top)	`node`	`k`	What it means
1	Dive: `stack.append(node)`, `node = node.left`	`[5, 3, 2, 1]`	`None`	3	Four nodes pushed, none counted: pushing is not visiting
2	`node = stack.pop()`, `k -= 1`	`[5, 3, 2]`	1	2	1st visit: 1 is the smallest value
3	`node = node.right` is `None`; pop, `k -= 1`	`[5, 3]`	2	1	2nd visit
4	`node = node.right` is `None`; pop, `k -= 1`	`[5]`	3	0	3rd visit: `k == 0`, return 3

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

Counting pushes instead would reach k == 0 at the third push, node 2, and return the wrong value.

Core Invariant Specification & Code Shape

Archetype Code Shape

Python

1	Rank in a BST is position in sorted order, and an inorder walk (left subtree, node, right subtree) visits the values in sorted order: the answer is the `k`-th visit.
2	When `stack.pop()` returns `node`, every smaller value has already been visited, so do `k -= 1` there and `return node.val` when `k == 0`.
3	Start with `stack = []` and `node = root`, and loop `while node or stack`: an inner `while node` pushes and moves to `node.left`, then pop, count, and move to `node.right`.
4	The trap: count on the pop, never on the push. Nodes are pushed from the root down, so counting pushes on `[3,1,4,null,2]` returns 3 for `k = 1`.

Target: Kth Smallest Element in a BST (LeetCode 230). Each node on the stack is an ancestor whose left subtree is still being walked.

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 k-th smallest value sounds like a job for sorting: copy every value out, sort, and index. A BST makes that unnecessary, because it is already sorted, just not in a line. Every value in a node's left subtree is smaller than the node, and every value in its right subtree is larger, so the order left subtree, node, right subtree (an inorder walk) visits the values from smallest to largest. BST Inorder reads the tree as that sorted list, one value per visit, and stops as soon as it has what it needs.

📚 The Analogy: A Library Shelved by Call Number

A library keeps its books in call-number order along branching aisles: every aisle to your left holds smaller numbers, every aisle to your right larger ones. To find the 10th book in call-number order, you don't pull every book off the shelves and sort them. You walk to the far left end, then walk the aisles in order, counting books as you pass them, and stop at the 10th. On the way in you note each turn you skipped (the stack), so you can come back to it.

🪄 The Mathematical Harmony / Magic Trick

Code / Blueprint

stack = []
node = root
while node or stack:
    while node:
        stack.append(node)
        node = node.left
    node = stack.pop()
    k -= 1
    if k == 0:
        return node.val
    node = node.right

The inner loop dives left, pushing every node it passes, so the node that stack.pop() returns has no smaller value left unvisited: its left subtree is done, and so is every ancestor it sits to the right of. Each pop is therefore the next value in sorted order, and k -= 1 on the pop counts ranks exactly. Counting on the push instead would count nodes from the root down, which is not sorted order.

💡 Summary

Dive left pushing onto stack, visit on stack.pop(), count with k -= 1 there, return at k == 0, and continue from node.right. The walk stops after k visits: $O(H + k)$ time and $O(H)$ space.

Counting on the push: k -= 1 belongs right after stack.pop(). Nodes are pushed from the root down, so counting pushes on [3,1,4,null,2] with k = 1 returns 3 instead of 1.
Looping on while stack alone: the stack starts empty, and it empties again after the root is visited while node still points at its right subtree. Loop on while node or stack.
Pushing the right child directly: after a visit, set node = node.right and let the inner loop dive left; pushing node.right visits it before its own left subtree ([2,1,4,null,null,3] returns 4 for k = 3).
Sorting everything: copying every value into a list and sorting it is correct but costs O(n log n) time and O(n) memory; the walk stops after k visits.

Senior SWE Reasoning Architecture

4-Phase Thought Process Model

You will see how a senior engineer turns a rank question on a BST into an inorder walk and defends where the count goes.

Pattern Recognition Signals

The 10-second spot

"Binary search tree" plus "the k-th smallest value": rank means position in sorted order, and in a BST the inorder walk (left subtree, node, right subtree) already produces sorted order. When a BST question is about ranks, neighbouring values or the values nearest a target, that is the signal for BST Inorder.

Formulating the Predicate & Invariants

Turning intuition into a boolean rule

When stack.pop() returns node, every value smaller than node.val has been visited and k counts the visits still needed. Visit, k -= 1; if k == 0, return node.val; otherwise continue from node.right.

Silent Failure Traps & Edge Cases

Where confident candidates still lose points

k -= 1 goes right after stack.pop(), not beside stack.append(node): nodes are pushed from the root down, so counting pushes on [3,1,4,null,2] with k = 1 returns 3 instead of 1.
while node or stack, not while stack: the stack is empty at the start, and again after visiting the root of [3,1,4,null,2] while node is 4.
Set node = node.right and let the inner loop dive; pushing node.right directly visits it before its left subtree ([2,1,4,null,null,3] would give 4 as the 3rd smallest).
Don't collect and sort every value: it is correct, but O(n log n) time and O(n) memory when k visits are enough.

The 60-Second Interview Pitch

Say this out loud before you type a single line

I'd use BST Inorder. In a binary search tree, visiting the left subtree, then the node, then the right subtree hands out the values in sorted order, so the k-th smallest is simply the k-th visit. I walk iteratively with a stack: going left, I push every node I pass, so when I pop a node, everything smaller than it has already been visited. On each pop I decrement k, and when k reaches zero I return that node's value; otherwise I continue from its right child. The trap is where I count: nodes are pushed from the root down, so counting pushes would return a value near the root instead of the k-th smallest. Counting pops keeps the count equal to the rank. I stop after k visits, so the time is O(H plus k), where H is the height of the tree, and the stack uses O(H) space.

So: rank is sorted position, the inorder walk is sorted order, and k -= 1 belongs on the pop, not the push.

Big-O Invariant Derivation

Complexity & Mathematical Proof

TIME COMPLEXITY

O(H + k)

Look at the code: before the first visit, the inner while node: loop pushes the left edge of the tree, at most H nodes. After that, each pass of the outer loop visits one node with stack.pop() and k -= 1, and every node pushed along the way is either visited later or still on stack when the function returns. The walk returns at the k-th visit, so it makes at most k pops and at most H + k pushes, each O(1). Total: O(H + k).

SPACE COMPLEXITY

O(H) stack

Every node on stack is an ancestor of node whose left subtree is still being walked, so stack holds at most one root-to-leaf path: O(H) nodes. The answer is one integer.

Formal Recurrence Relation

$T(n) = O(H) + k \cdot O(1) = O(H + k)$

Derivation Progression

First dive

at most H pushes

Before the first visit, while node: pushes the left edge of the tree, one node per level.

Visits

k pops

Each pass of while node or stack: pops one node and runs k -= 1; the function returns at the k-th pop.

Pushes after the first dive

at most H + k pushes in total

Every pushed node is either popped (at most k of them) or still on stack at the return (at most H).

Total

O(H + k)

Each push and pop is O(1).

Variable Definitions

$n$

Number of nodes in the tree

$H$

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

$k$

The rank asked for, 1 <= k <= n

Memory Architecture & Bounds

🟣 Call Stack

O(1): iterative, no recursion

🔵 Auxiliary Heap

O(H): stack holds one root-to-leaf path at most

🟢 Output Space

O(1): one integer

Boundary Best / Worst Cases

Best Case

$O(H)$ : k = 1, one dive down the left edge and a single visit

Average Case

$O(\log n + k)$ on a balanced tree

Worst Case

$O(n)$ : k = n, or a chain of height $n$

Graph & Tree Traversal Frontier

Synthesizing vector architecture diagram...

Staff+ Engineering Perspective

Senior SWE Deconstruction & Hardware Caveats

ARCHITECTURAL SIGNALS & INTERVIEW TRIGGERS

Triggers: "binary search tree", **"the k-th smallest value"**. Rank in a BST is position in sorted order, and an inorder walk hands out the values already sorted: BST Inorder, read as a stream that stops after k visits.

CONSTRAINTS & BOUNDS

$n \le 10^4$ nodes, $1 \le k \le n$ . Copying every value into a list and sorting costs $O(n \log n)$ time and $O(n)$ memory; the iterative walk stops after k visits, so it costs $O(H + k)$ time and only the $O(H)$ stack, where $H$ is the tree height ( $\log n$ when balanced, up to $n$ on a chain).

FAANG PRODUCTION TRAPS & EDGE CASES

Counting a node when it is pushed instead of when it is popped returns a value near the root, not the k-th smallest. A chain of $10^4$ nodes is $10^4$ levels deep: a recursive walk can overflow a small call stack, and the explicit stack avoids that. LeetCode's follow-up (many queries while nodes are inserted and deleted) calls for storing each node's subtree size, so one query walks a single root-to-leaf path in $O(H)$ .

Core Algorithmic State Invariants

1. Inorder = Sorted Order

In a BST every left-subtree value is smaller than the node and every right-subtree value larger, so the walk left subtree, node, right subtree visits the values in ascending order.

2. Count on the Visit

`k -= 1` runs right after `stack.pop()`, the moment a node is visited. Nodes are pushed from the root down, so counting pushes would return a value near the root, not the k-th smallest.

3. Stop After k Visits

The walk returns at the k-th visit: one dive of at most H pushes, then k pops, so O(H + k) time, and `stack` never holds more than H nodes.

Theory Context•Depth-First Search (DFS)

MediumLC 230

Kth Smallest Element in a BST (LeetCode 230)

You will see how an inorder walk reads a BST as a sorted list and stops at the k-th value.

Target Frequency:AmazonMetaGoogle

In a binary search tree, the values in a node's left subtree are smaller than the node's value, and the values in its right subtree are larger.

Follow-up: if nodes are inserted and deleted often and this question is asked again and again, how would you make each answer faster?

Worked Examples

Example 1

Input:root = [3,1,4,null,2], k = 1

Output:1

Explanation: Written smallest first, the values are `1, 2, 3, 4`. Position 1 holds `1`, a leaf on the left, even though `3` sits at the top of the tree.

Example 2

Input:root = [5,3,6,2,4,null,null,1], k = 3

Output:3

Explanation: Written smallest first, the values are `1, 2, 3, 4, 5, 6`, so position 3 holds `3`.

⚖️Formal Constraints & Bounds

The number of nodes in the tree is n.
1 <= k <= n <= 10⁴
0 <= Node.val <= 10⁴

Deep-Dive & Conceptual Insights

Why It Works & Core Invariant

Rank in a BST is position in sorted order, and the inorder walk produces sorted order one value per visit, so the k-th visit is the answer and the walk can stop there.

Real-World Scenario & Production Applications

Step-by-Step Execution Trace Table

Example 2, root = [5,3,6,2,4,null,null,1], k = 3:

Step	What runs	`stack` (bottom to top)	`node`	`k`	What it means
1	Dive: `stack.append(node)`, `node = node.left`	`[5, 3, 2, 1]`	`None`	3	Four nodes pushed, none counted: pushing is not visiting
2	`node = stack.pop()`, `k -= 1`	`[5, 3, 2]`	1	2	1st visit: 1 is the smallest value
3	`node = node.right` is `None`; pop, `k -= 1`	`[5, 3]`	2	1	2nd visit
4	`node = node.right` is `None`; pop, `k -= 1`	`[5]`	3	0	3rd visit: `k == 0`, return 3

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

Counting pushes instead would reach k == 0 at the third push, node 2, and return the wrong value.

Trace Inputroot = [3,1,4,null,2], k = 1

Expected1

Example 2, root = [5,3,6,2,4,null,null,1], k = 3:

Step	What runs	`stack` (bottom to top)	`node`	`k`	What it means
1	Dive: `stack.append(node)`, `node = node.left`	`[5, 3, 2, 1]`	`None`	3	Four nodes pushed, none counted: pushing is not visiting
2	`node = stack.pop()`, `k -= 1`	`[5, 3, 2]`	1	2	1st visit: 1 is the smallest value
3	`node = node.right` is `None`; pop, `k -= 1`	`[5, 3]`	2	1	2nd visit
4	`node = node.right` is `None`; pop, `k -= 1`	`[5]`	3	0	3rd visit: `k == 0`, return 3

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

Counting pushes instead would reach k == 0 at the third push, node 2, and return the wrong value.

Core Invariant Specification & Code Shape

Archetype Code Shape

Python

1	Rank in a BST is position in sorted order, and an inorder walk (left subtree, node, right subtree) visits the values in sorted order: the answer is the `k`-th visit.
2	When `stack.pop()` returns `node`, every smaller value has already been visited, so do `k -= 1` there and `return node.val` when `k == 0`.
3	Start with `stack = []` and `node = root`, and loop `while node or stack`: an inner `while node` pushes and moves to `node.left`, then pop, count, and move to `node.right`.
4	The trap: count on the pop, never on the push. Nodes are pushed from the root down, so counting pushes on `[3,1,4,null,2]` returns 3 for `k = 1`.

Target: Kth Smallest Element in a BST (LeetCode 230). Each node on the stack is an ancestor whose left subtree is still being walked.

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: A Library Shelved by Call Number

🪄 The Mathematical Harmony / Magic Trick

Code / Blueprint

stack = []
node = root
while node or stack:
    while node:
        stack.append(node)
        node = node.left
    node = stack.pop()
    k -= 1
    if k == 0:
        return node.val
    node = node.right

💡 Summary

Counting on the push: k -= 1 belongs right after stack.pop(). Nodes are pushed from the root down, so counting pushes on [3,1,4,null,2] with k = 1 returns 3 instead of 1.
Looping on while stack alone: the stack starts empty, and it empties again after the root is visited while node still points at its right subtree. Loop on while node or stack.
Pushing the right child directly: after a visit, set node = node.right and let the inner loop dive left; pushing node.right visits it before its own left subtree ([2,1,4,null,null,3] returns 4 for k = 3).
Sorting everything: copying every value into a list and sorting it is correct but costs O(n log n) time and O(n) memory; the walk stops after k visits.

Senior SWE Reasoning Architecture

4-Phase Thought Process Model

You will see how a senior engineer turns a rank question on a BST into an inorder walk and defends where the count goes.

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

k -= 1 goes right after stack.pop(), not beside stack.append(node): nodes are pushed from the root down, so counting pushes on [3,1,4,null,2] with k = 1 returns 3 instead of 1.
while node or stack, not while stack: the stack is empty at the start, and again after visiting the root of [3,1,4,null,2] while node is 4.
Set node = node.right and let the inner loop dive; pushing node.right directly visits it before its left subtree ([2,1,4,null,null,3] would give 4 as the 3rd smallest).
Don't collect and sort every value: it is correct, but O(n log n) time and O(n) memory when k visits are enough.

The 60-Second Interview Pitch

Say this out loud before you type a single line

I'd use BST Inorder. In a binary search tree, visiting the left subtree, then the node, then the right subtree hands out the values in sorted order, so the k-th smallest is simply the k-th visit. I walk iteratively with a stack: going left, I push every node I pass, so when I pop a node, everything smaller than it has already been visited. On each pop I decrement k, and when k reaches zero I return that node's value; otherwise I continue from its right child. The trap is where I count: nodes are pushed from the root down, so counting pushes would return a value near the root instead of the k-th smallest. Counting pops keeps the count equal to the rank. I stop after k visits, so the time is O(H plus k), where H is the height of the tree, and the stack uses O(H) space.

So: rank is sorted position, the inorder walk is sorted order, and k -= 1 belongs on the pop, not the push.

Big-O Invariant Derivation

Complexity & Mathematical Proof

TIME COMPLEXITY

O(H + k)

SPACE COMPLEXITY

O(H) stack

Every node on stack is an ancestor of node whose left subtree is still being walked, so stack holds at most one root-to-leaf path: O(H) nodes. The answer is one integer.

Formal Recurrence Relation

$T(n) = O(H) + k \cdot O(1) = O(H + k)$

Derivation Progression

First dive

at most H pushes

Before the first visit, while node: pushes the left edge of the tree, one node per level.

Visits

k pops

Each pass of while node or stack: pops one node and runs k -= 1; the function returns at the k-th pop.

Pushes after the first dive

at most H + k pushes in total

Every pushed node is either popped (at most k of them) or still on stack at the return (at most H).

Total

O(H + k)

Each push and pop is O(1).

Variable Definitions

$n$

Number of nodes in the tree

$H$

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

$k$

The rank asked for, 1 <= k <= n

Memory Architecture & Bounds

🟣 Call Stack

O(1): iterative, no recursion

🔵 Auxiliary Heap

O(H): stack holds one root-to-leaf path at most

🟢 Output Space

O(1): one integer

Boundary Best / Worst Cases

Best Case

$O(H)$ : k = 1, one dive down the left edge and a single visit

Average Case

$O(\log n + k)$ on a balanced tree

Worst Case

$O(n)$ : k = n, or a chain of height $n$

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. Inorder = Sorted Order

In a BST every left-subtree value is smaller than the node and every right-subtree value larger, so the walk left subtree, node, right subtree visits the values in ascending order.

2. Count on the Visit

`k -= 1` runs right after `stack.pop()`, the moment a node is visited. Nodes are pushed from the root down, so counting pushes would return a value near the root, not the k-th smallest.

3. Stop After k Visits

The walk returns at the k-th visit: one dive of at most H pushes, then k pops, so O(H + k) time, and `stack` never holds more than H nodes.

Rosetta Dual-Monaco Comparison

Python 3

CANONICAL INVARIANT TEMPLATE

CONCRETE: KTH SMALLEST ELEMENT IN A BST (LEETCODE 230)

T = O(H + k)S = O(H) stack

Pattern Implementation Mapping TableCanonical Invariant ⟷ Concrete Code ⟷ Engineering Rationale

Canonical Invariant	Concrete Code	Engineering Rationale
Nodes waiting for their visit	`stack: list[TreeNode] = []`	Each node on the stack is an ancestor whose left subtree is still being walked.
Start at the root	`node = root`	The walk begins at the top; nothing has been visited yet.
Walk until nothing is left	`while node or stack:`	Unvisited nodes are either below `node` or waiting on `stack`; the loop ends only when both are gone.
Dive left, pushing every node	`while node: stack.append(node) node = node.left`	Every smaller value sits in a left subtree, so go as far left as possible first.
Visit the next value in sorted order	`node = stack.pop()`	Everything smaller than the popped node has been visited already.
Count on the visit (the trap)	`k -= 1`	Counting here keeps `k` tied to the rank; counting on the push would follow the order nodes are pushed in, root first.
Stop at the k-th visit	`if k == 0: return node.val`	The k-th value out of the stack is the k-th smallest.
Move on to the next larger values	`node = node.right`	The right subtree holds the values just above `node.val`; the next pass dives left inside it.

Step

What runs

stack (bottom to top)

node

k

What it means

Dive: stack.append(node), node = node.left

[5, 3, 2, 1]

None

Four nodes pushed, none counted: pushing is not visiting

node = stack.pop(), k -= 1

[5, 3, 2]

1st visit: 1 is the smallest value

node = node.right is None; pop, k -= 1

[5, 3]

2nd visit

node = node.right is None; pop, k -= 1

[5]

3rd visit: k == 0, return 3

Step

What runs

stack (bottom to top)

node

k

What it means

Dive: stack.append(node), node = node.left

[5, 3, 2, 1]

None

Four nodes pushed, none counted: pushing is not visiting

node = stack.pop(), k -= 1

[5, 3, 2]

1st visit: 1 is the smallest value

node = node.right is None; pop, k -= 1

[5, 3]

2nd visit

node = node.right is None; pop, k -= 1

[5]

3rd visit: k == 0, return 3

Step

What runs

stack (bottom to top)

node

k

What it means

Dive: stack.append(node), node = node.left

[5, 3, 2, 1]

None

Four nodes pushed, none counted: pushing is not visiting

node = stack.pop(), k -= 1

[5, 3, 2]

1st visit: 1 is the smallest value

node = node.right is None; pop, k -= 1

[5, 3]

2nd visit

node = node.right is None; pop, k -= 1

[5]

3rd visit: k == 0, return 3

Step

What runs

stack (bottom to top)

node

k

What it means

Dive: stack.append(node), node = node.left

[5, 3, 2, 1]

None

Four nodes pushed, none counted: pushing is not visiting

node = stack.pop(), k -= 1

[5, 3, 2]

1st visit: 1 is the smallest value

node = node.right is None; pop, k -= 1

[5, 3]

2nd visit

node = node.right is None; pop, k -= 1

[5]

3rd visit: k == 0, return 3

🧭 Conceptual Foundation & Pattern Intuition

📚 The Analogy: A Library Shelved by Call Number

🪄 The Mathematical Harmony / Magic Trick

Code / Blueprint

stack = []
node = root
while node or stack:
    while node:
        stack.append(node)
        node = node.left
    node = stack.pop()
    k -= 1
    if k == 0:
        return node.val
    node = node.right

💡 Summary

Canonical Invariant

Concrete Code

Engineering Rationale

Nodes waiting for their visit

stack: list[TreeNode] = []

Each node on the stack is an ancestor whose left subtree is still being walked.

Start at the root

node = root

The walk begins at the top; nothing has been visited yet.

Walk until nothing is left

while node or stack:

Unvisited nodes are either below `node` or waiting on `stack`; the loop ends only when both are gone.

Dive left, pushing every node

while node:
    stack.append(node)
    node = node.left

Every smaller value sits in a left subtree, so go as far left as possible first.

Visit the next value in sorted order

node = stack.pop()

Everything smaller than the popped node has been visited already.

Count on the visit (the trap)

k -= 1

Counting here keeps `k` tied to the rank; counting on the push would follow the order nodes are pushed in, root first.

Stop at the k-th visit

if k == 0:
    return node.val

The k-th value out of the stack is the k-th smallest.

Move on to the next larger values

node = node.right

The right subtree holds the values just above `node.val`; the next pass dives left inside it.