LeetCode 230 · Medium · Trees

Kth Smallest Element in a BST

Given a binary search tree and a number k, return the k-th smallest value in it, counting from 1.

O(h + k)time
O(h)space · explicit stack
in-orderiterative, stop at the k-th pop

a valid BST in level order, distinct values · 1 to 15 nodes, 4 levels · values −99 to 99 · 1 ≤ k ≤ nodes

stack nodes waiting for their turn · top on the right · badges on the tree = pop order n

Popped in order sorted, smallest first

public int kthSmallest(TreeNode root, int k) { int n = 0; Deque<TreeNode> stack = new ArrayDeque<>(); TreeNode cur = root; while (cur != null || !stack.isEmpty()) { while (cur != null) { stack.push(cur); cur = cur.left; } cur = stack.pop(); n++; if (n == k) { return cur.val; } cur = cur.right; } return -1; // never reached: 1 <= k <= n}
k
—
n
0
cur
—
stack
[]

Why it works

  1. Brute force collects all values, sorts them and indexes k − 1: O(n log n) time, O(n) space, and it ignores the BST order completely.
  2. In-order traversal of a BST visits values in sorted order. So the k-th node popped is the answer. The stack holds the path of left turns still waiting: a node is popped only after everything smaller than it.
  3. Cost: the walk first dives down the left spine (up to h pushes), then pops k nodes, each followed by at most a short dive: O(h + k) time. The stack never holds more than one path: O(h) space.
  4. Pitfall: counting when a node is pushed instead of when it is popped. Pushes happen top-down along a path, which is not sorted; only pops come out in order.
  5. Follow-up: if the tree changes often and k-th queries are frequent, store the size of each subtree in its node; then each query walks one path, O(h).