230. Kth Smallest Element in a BST

230

MediumTrees and Binary Search TreesBST inorder traversal with a stackInorder traversal counts up to k

Kth Smallest Element in a BST

Given the root of a binary search tree and an integer k, return the k-th smallest value (1-indexed) among all node values in the tree.

Open official problem prompt ↗

In plain English

Find the value of rank k in sorted order without materializing the entire sorted list.

Picture it like this

Reading a sorted ledger from the top: you count entries one by one and stop the instant you reach line k, never reading the rest.

Example

Input: root = [3,1,4,null,2], k = 1
Output: 1
Why: An inorder walk of the BST yields values in sorted order [1,2,3,4]; the 1st smallest is 1.

Constraints

The number of nodes is n, with 1 <= k <= n <= 10^40 <= Node.val <= 10^4

Pattern lesson

See the pattern, then code

Inorder traversal counts up to k

↗

Trees and Binary Search Trees

Hierarchies, subtree aggregation, path properties, or ordered tree queries.. An inorder traversal of a BST emits values in sorted order, so the k-th value it emits is exactly the k-th smallest; stop as soon as the count reaches k.

New words, made simpleKnow these before the algorithm

Binary search tree (BST): A tree where every left descendant is smaller and every right descendant is larger than a node.
Inorder traversal: Visit left subtree, then node, then right subtree; on a BST this yields sorted order.
Iterative traversal: Simulating recursion with an explicit stack so you can stop early.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Full inorder into a list

Works but visits every node even when k is small, and stores the whole list.

Collect all values in sorted order, then index k-1.

Time O(n)Space O(n)

Best choiceIterative inorder with early stop

Stops as soon as the answer is found and only holds one root-to-node path.

Emit values one at a time and return once the k-th is reached.

Time O(h + k)Space O(h)

The rule we keep true

Invariant

Every node already popped from the stack is smaller than every node not yet visited, so the pop count equals the current rank.

Why this is correct

Reasoning

The stack always holds the ancestors along the leftmost unexplored path. Popping yields the smallest unvisited value, so the k-th pop is the k-th smallest by definition of inorder order on a BST.

The algorithm in three movesSay these aloud before coding

1Walk left as far as possible, pushing nodes onto a stack

push 3, push 1

2Pop a node (the next smallest) and decrement k

pop 1 -> k=0 -> return 1

3If k hits 0, return that node's value

4Otherwise move into the node's right subtree and repeat

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1 · Readroot 3

2 · AskAny smaller node?

3 · Update statestack=[3]; go to 1

4 · Resultpush 1, its left is None

Key takeaway

Inorder order of the BST is 1,2,3,4; k=1 stops at the first popped value.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 3-4Set up
An explicit stack and a moving pointer replace recursion so we can bail out early.
2
Lines 6-8Go left
Push every node while walking to the smallest remaining value.
3
Lines 9-13Visit and count
Pop the next smallest, decrement k, return when it hits 0, else pivot into the right subtree.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

k = 1 returns the leftmost node
k = n returns the maximum value
A node with only a right child still traverses correctly

Common beginner mistakes

Off-by-one from treating k as 0-indexed; the problem is 1-indexed
Decrementing k before popping, which shifts the count
Rebuilding the whole sorted list when an early exit is available

Check your understanding

If the BST supported frequent kthSmallest queries with insertions between them, what would you change?

Kth Smallest Element in a BST

Kth Smallest Element in a BST

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Trees and Binary Search Trees