Kth Smallest and Largest in BST
Find both the k-th smallest and k-th largest BST values.
Open on GeeksforGeeks ↗02
Intuition
k-th smallest is the k-th node of inorder (left-node-right); k-th largest is the k-th node of REVERSE inorder (right-node-left). Two early-stopping traversals — or one, since k-th largest = (n−k+1)-th smallest.
03
Approach
1
Forward inorder for smallest
Count nodes as visited; stop at k.
2
Reverse inorder for largest
Mirror the traversal (right first) — descending stream, stop at k.
3
Or count once
Knowing n converts largest into a second smallest query; useful when n is cached.
04
Solution & live demo
python
▶1def kth_smallest_largest(root, k):
▶2 def inorder(node, reverse, count, out):
▶3 if not node or out: return
▶4 a, b = (node.right, node.left) if reverse else (node.left, node.right)
▶5 inorder(a, reverse, count, out)
▶6 if not out:
▶7 count[0] += 1
▶8 if count[0] == k: out.append(node.val); return
▶9 inorder(b, reverse, count, out)
▶10 small, large = [], []
▶11 inorder(root, False, [0], small)
▶12 inorder(root, True, [0], large)
▶13 return small[0], large[0]
05
Edge cases
k = 1
Smallest = leftmost node, largest = rightmost.
k > n
Traversal exhausts → report not found.
06
Complexity
Time
O(h + k)
Space
O(h)
Two early-exit traversals.