Kth Smallest Element in a BST

Return the kth smallest tree value.

Start with the concrete trace below. It shows the state the algorithm must carry as it runs.

Problem trace

Kth Smallest Element in a BST: Iterative inorder exposes BST values in ascending order, so the fourth pop is the answer.

Input and goalReturn the `k`th smallest tree value.

Initialize traversalSet root=5, stack=[], and remaining k=4.

5root=5/\37/\/\2468|1

inputtree=[5,3,7,2,4,6,8,1], k=4cursorroot=5stack[]remaining4

Recognize it

The input is a BST and the question asks for an order statistic, so inorder traversal produces the required sorted rank without sorting all values.

Keep true

Before each pop, the stack top is the smallest unvisited node reachable from the processed search frontier; completed pops are in strictly ascending BST order.

Reuse it

Use inorder as a sorted stream for BST rank, range, predecessor, and successor tasks, and stop as soon as the requested portion of that stream is consumed.

Pattern: Iterative inorder traversal.

Simple idea: Inorder visits BST values from smallest to largest. Stop at the kth visited node.

def kth_smallest(root: TreeNode | None, k: int) -> int:
   stack: list[TreeNode] = []

   while root or stack:
      while root:
         stack.append(root)
         root = root.left
      root = stack.pop()
      k -= 1
      if k == 0:
         return root.val
      root = root.right
   raise ValueError("k is larger than the tree")

Cost: $O(h+k)$ time and $O(h)$ space.

The platform supplies TreeNode with val, left, and right; this snippet assumes that definition.