Kth Smallest Element in a BST
FreeTreesMedium32 of 75
The problem
Given a BST with distinct values and a valid one-based rank k, return its kth smallest value.
Example
Values {2, 5, 7, 9}, k = 3 → 7
Need a hint?
In-order traversal of a BST produces sorted values.
Write pseudocode, trace the example, or note an edge case. This scratchpad does not run code.
Notes stay in this browser when storage is available.
Read the solution approach
Use a stack to descend to the leftmost unvisited node. Pop and count one visited value, returning when the count reaches k. Then traverse its right subtree by pushing that subtree’s left spine. Stop early rather than materializing every value.
Complexity
O(h + k) time and O(h) space.
Before moving on, explain why the algorithm is correct and trace a boundary case without looking at the approach.