Kth Smallest in BST

LeetCode 230 • Medium • Trees

Input: root = [3,1,4,null,2], k = 3 → Output: 3
Inorder traversal visits nodes in sorted order. Return the k-th visited value.

TimeO(h + k)push left chain + k pops

SpaceO(h)stack depth

Stack: []Count: 0

Current

In Stack

Visited (inorder)

Stack

[]

Count

Speed:

Ready

Press Play. Iterative inorder: push left chain, pop and count. When count == k, return node.val.

✎ Whiteboard

Size:3

⌨ Type It — Iterative

Practice until you don't need to look. Inorder iterative: push left chain, pop, count, go right.

═══ KTH SMALLEST BST — ITERATIVE INORDER ═══

PATTERN ▸ Inorder (push left, pop, count, go right) O(n) · O(h)

① INIT

stack = []; cur = root

② INORDER LOOP

while cur or stack:

while cur: stack.append(cur); cur = cur.left

cur = stack.pop(); count += 1

if count == k: return cur.val

cur = cur.right

▼ your implementation ▼

Verify your solution:

⌨ Type It — Recursive

Practice until you don't need to look. Inorder DFS: left, visit (count), right.

═══ KTH SMALLEST BST — RECURSIVE INORDER ═══

PATTERN ▸ Inorder DFS (left, visit, right) O(n) · O(h)

① BASE CASE

if not node: return

② RECURSE LEFT

inorder(node.left)

③ VISIT & CHECK

count += 1; if count == k: result = node.val

④ RECURSE RIGHT

inorder(node.right)

▼ your implementation ▼

Verify your solution: