Kth Smallest Element in a BST Visualizer (Inorder)

Kth Smallest Element: how it works

Inorder traversal of a BST visits nodes in sorted (ascending) order. Count nodes as you visit them. The kth one is the answer.

1. Inorder = Sorted

   BST inorder traversal yields nodes in ascending order. Kth smallest is simply the kth node visited.

2. Count as You Visit

   Maintain a counter. Increment it each time you "visit" a node (after returning from left subtree). Stop when count reaches k.

3. Early Termination

   Once the kth node is found, stop recursing. You do not need to visit the rest of the tree.

4. Follow-up: Frequent Queries

   If kth smallest is queried repeatedly, augment each node with a left-subtree count. Then each query is O(h) instead of O(k).

Complexity

Best-case time

O(k)

Average time

O(h + k)

Worst-case time

O(N)

Space

O(h)

LeetCode 230. The inorder traversal stack depth is O(h). For a balanced BST this is O(log N); for a skewed tree it is O(N).