Kth Smallest Element in a BST

Medium#230in-order

You get the root of a binary search tree and a number k. Return the k-th smallest value in the tree, counting from 1. Our tree: 13 with children 7 and 18; 7 has children 3 and 10; 10 has a left child, 8; 18 has a right child, 25. k = 4 — the answer is 10.

230 Kth Smallest Element in a BSTWalkthrough · 1×

Example: the 4th smallest value of a binary search tree: walk it in order with a stack and stop at the 4th value.

nonenonenonenonenonenonenonenone13718310258in order—stacktop on the right—
not reachedon the stackcurcounted, #n is its place in sorted ordernone: an empty child

stack = []; we need the 4th smallest value

01/41
restart · back · play · step
Speed
1function kthSmallest(root, k):
2 stack = []
3 cur = root
4 while true:
5 while cur is not none:
6 stack.push(cur)
7 cur = cur.left
8 cur = stack.pop()
9 k = k - 1
10 if k == 0:
11 return cur.val
12 cur = cur.right
state
k
4
cur
–
stack
[]
historyclick a step to go back

← → step · space play/pause

Why it works

  1. In a binary search tree, in-order gives the values from smallest to largest, so the k-th value popped is the k-th smallest.
  2. The stack lets the walk stop in the middle: once k reaches 0 we return, and the nodes still waiting or never reached cost nothing.

Complexity

Time O(h + k), where h is the height of the tree: one path down to the smallest value, then k pops. Memory O(h): the stack holds one path.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.