176. Kth Smallest in BST

Why this mechanism works

Inorder of a BST is increasing, so ranking becomes counting emission events. An explicit stack performs the left descent, then emits the next smallest node and moves to its right subtree. The stack contains unfinished ancestors rather than all values in sorted order.

State and boundaries

stack holds ancestors waiting for their inorder emission. k is the number of remaining emissions needed to reach the requested rank.

Protocol

1. Reject nonpositive k.
2. Push the entire current left spine.
3. Pop and emit the next node, decrementing k.
4. Return its value when k becomes zero.
5. Continue from its right child.
6. Reject if traversal ends first.

Visualization

BST values in inorder: 1 -> 2 -> 3 -> 4
k starts 3; remaining: 2,1,0
return at the third pop, without collecting all values

Python implementation

from structures import build_tree

def kth_smallest_bst(root, k):
    if k <= 0:
        raise ValueError('k must be positive')
    stack, node = [], root
    while node is not None or stack:
        while node is not None:
            stack.append(node)
            node = node.left
        node = stack.pop()
        k -= 1
        if k == 0:
            return node.val
        node = node.right
    raise ValueError('rank exceeds tree size')

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L4 kth_smallest_bst: if k <= 0:
root=N1(val=3,left=N2,right=N3); k=3

L6 kth_smallest_bst: stack, node = [], root
root=N1(val=3,left=N2,right=N3); k=3; stack=[]; node=N1(val=3,left=N2,right=N3)

L9 kth_smallest_bst: stack.append(node)
root=N1(val=3,left=N2,right=N3); k=3; stack=[N1(val=3,left=N2,right=N3)]; node=N1(val=3,left=N2,right=N3)

L10 kth_smallest_bst: node = node.left
root=N1(val=3,left=N2,right=N3); k=3; stack=[N1(val=3,left=N2,right=N3)]; node=N2(val=1,left=None,right=N4)

L9 kth_smallest_bst: stack.append(node)
root=N1(val=3,left=N2,right=N3); k=3; stack=[N1(val=3,left=N2,right=N3), N2(val=1,left=None,right=N4)]; node=N2(val=1,left=None,right=N4)

L10 kth_smallest_bst: node = node.left
root=N1(val=3,left=N2,right=N3); k=3; stack=[N1(val=3,left=N2,right=N3), N2(val=1,left=None,right=N4)]; node=None

L11 kth_smallest_bst: node = stack.pop()
root=N1(val=3,left=N2,right=N3); k=3; stack=[N1(val=3,left=N2,right=N3)]; node=N2(val=1,left=None,right=N4)

L12 kth_smallest_bst: k -= 1
root=N1(val=3,left=N2,right=N3); k=2; stack=[N1(val=3,left=N2,right=N3)]; node=N2(val=1,left=None,right=N4)

... 4 intermediate state changes omitted ...

L12 kth_smallest_bst: k -= 1
root=N1(val=3,left=N2,right=N3); k=1; stack=[N1(val=3,left=N2,right=N3)]; node=N4(val=2,left=None,right=None)

L15 kth_smallest_bst: node = node.right
root=N1(val=3,left=N2,right=N3); k=1; stack=[N1(val=3,left=N2,right=N3)]; node=None

L11 kth_smallest_bst: node = stack.pop()
root=N1(val=3,left=N2,right=N3); k=1; stack=[]; node=N1(val=3,left=N2,right=N3)

L12 kth_smallest_bst: k -= 1
root=N1(val=3,left=N2,right=N3); k=0; stack=[]; node=N1(val=3,left=N2,right=N3)

L4 kth_smallest_bst: if k <= 0:
root=N1(val=2,left=N2,right=N3); k=1

L6 kth_smallest_bst: stack, node = [], root
root=N1(val=2,left=N2,right=N3); k=1; stack=[]; node=N1(val=2,left=N2,right=N3)

L9 kth_smallest_bst: stack.append(node)
root=N1(val=2,left=N2,right=N3); k=1; stack=[N1(val=2,left=N2,right=N3)]; node=N1(val=2,left=N2,right=N3)

L10 kth_smallest_bst: node = node.left
root=N1(val=2,left=N2,right=N3); k=1; stack=[N1(val=2,left=N2,right=N3)]; node=N2(val=1,left=None,right=None)

L9 kth_smallest_bst: stack.append(node)
root=N1(val=2,left=N2,right=N3); k=1; stack=[N1(val=2,left=N2,right=N3), N2(val=1,left=None,right=None)]; node=N2(val=1,left=None,right=None)

L10 kth_smallest_bst: node = node.left
root=N1(val=2,left=N2,right=N3); k=1; stack=[N1(val=2,left=N2,right=N3), N2(val=1,left=None,right=None)]; node=None

L11 kth_smallest_bst: node = stack.pop()
root=N1(val=2,left=N2,right=N3); k=1; stack=[N1(val=2,left=N2,right=N3)]; node=N2(val=1,left=None,right=None)

L12 kth_smallest_bst: k -= 1
root=N1(val=2,left=N2,right=N3); k=0; stack=[N1(val=2,left=N2,right=N3)]; node=N2(val=1,left=None,right=None)

Why the solution is correct

Every pop is the next inorder node because all of its left subtree is complete and its right subtree has not begun. BST ordering makes these emissions globally increasing. The kth pop therefore has the requested rank; exhaustion proves that rank does not exist.

Time and space

O(h+k) time for a valid rank, bounded by O(n), and O(h) auxiliary stack space. Invalid large k requires O(n) traversal.

Common mistakes

Using zero-based counting with a one-based contract returns the wrong rank. A BST can be skewed, so O(log n) height is not guaranteed.

Reasoning card

Transfer exercise

Augment nodes with subtree sizes to answer repeated rank queries without traversing k nodes.