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

Why this is worth learning

Inorder traversal turns strict BST order into rank order. A stack can pause that traversal after the kth visit instead of materializing every value.

Before coding: one-minute experiment

In a BST whose inorder values are [1,3,4,8], how many pops identify k=3 and what value is returned?

Function signature

func KthSmallest(root *TreeNode, k int) int

Inputs / outputs

• root: root of the BST.
• k: 1-indexed rank.
• Return: the k-th smallest value.

Example

    3
   / \
  1   4
   \
    2
k = 1
Output: 1

Constraints

• 1 <= number of nodes <= 100_000
• 1 <= k <= number of nodes

Core idea (near-solution)

Collecting and sorting all values would answer a rank query, but a valid BST has already encoded the order: left values, then root, then right values. Inorder therefore yields a sorted stream without sorting again. Stop after consuming k entries rather than materializing the entire stream. To pause recursion, store pending ancestors on a stack and push each left spine. Popping is the visit that consumes a rank; pushing is merely scheduling. The valid-BST and valid-k promises justify both the ordering and eventual success.

Invariant: before visiting a node, all nodes in its left subtree are smaller and already counted.

Algorithm (step-by-step)

1. Use an explicit stack for iterative inorder.
2. Walk left as far as possible, pushing nodes.
3. Pop a node, decrement k. If k == 0, return its value.
4. Move to the right child and repeat.

Correctness sketch

Pushing a left spine postpones each node until all smaller values in its left subtree have been considered. The stack top is then the smallest unvisited node. Popping it consumes exactly the next inorder rank, so decrementing k once per pop finds the kth smallest when k reaches zero. Moving into the popped node's right subtree and pushing its left spine restores the same next-smallest invariant. Every value emitted before termination is strictly earlier in sorted order, and the valid rank promise guarantees a kth visit exists.

Trace (hand walkthrough)

Example input:
    3
   / \
  1   4
   \
    2
k = 1
Output: 1

Walk:
- inorder traversal yields [1,2,3,4]
- k=1 -> answer 1

Pitfalls to avoid

• Not stopping when k reaches 0 (extra traversal).
• Forgetting to push the left spine before popping.

Debugging lens

Test k=1, k=node count, and a skewed tree. Do not decrement k while merely pushing the left spine.

Complexity

Time: O(h+k) to reach the kth visit, bounded by O(n) overall; this is an upper bound, not merely a best-case statement. Auxiliary space: O(h) for the explicit stack.

Implementation notes (Go)

• Use an explicit stack and push the left spine before popping.
• Decrement k on each pop and return when it reaches 0.

Reconstruction checkpoint

A BST has root 10, left child 6 with children 2 and 8, and right leaf 14. For k=3, show the pending stack before each pop. Which actions consume a rank?

Return to Binary Search Tree · Module quiz