Kth Smallest and Largest in BST
Kth Smallest Element In Bst: find both the k-th smallest and k-th largest BST values.
- 1 <= k <= number of nodes <= 10⁵
- 1 <= node value <= 10⁹
- All values are distinct
Intuition
This problem asks for the kth smallest and largest in bst — two values at once, the k-th smallest and the k-th largest. The naive route is to flatten the whole tree into a sorted array and index into it from both ends. That works, but it does O(n) work and O(n) extra space no matter how small k is, which is wasteful when you only need the third value out of a million.
The property to lean on is that an inorder traversal of a BST — left, then node, then right — emits values in ascending order. That is not a coincidence; it is the BST invariant read out loud. So the k-th node an inorder traversal visits is the k-th smallest value, and you can stop the instant your counter reaches k rather than finishing the traversal.
The k-th largest needs the same idea reflected. Run the traversal in reverse order — right, then node, then left — and the values come out descending, so the k-th node visited is the k-th largest. Two traversals, each stopping early, each costing O(h + k).
There is a shortcut worth knowing if you already have the node count n:
- The k-th largest is the (n − k + 1)-th smallest, so one forward traversal can answer both.
That trade is only worth it when n is already cached; computing it costs a full O(n) pass, which is exactly what the early-stopping traversals were designed to avoid.
In-order gives ascending values; reverse in-order — right, node, left — gives descending. So the k-th largest is the k-th smallest of the mirrored traversal, and one parameterised function answers both. Recognising that a traversal's direction is just a swap of two recursive calls saves writing the second algorithm.
Approach
Before reading on: price up what the direct approach costs here, then ask what each node needs from its children before it can answer. Aim for O(h + k) time and O(h) space.
Know why inorder gives you sorted order
For any node, a BST keeps everything smaller in the left subtree and everything larger in the right. Visiting left, then the node, then right therefore emits values from smallest to largest. This single fact is what makes the problem O(h + k) instead of O(n log n) — no sorting step is ever needed.
Walk the left spine with an explicit stack
Start at the root and push nodes while moving left until you hit null. The stack now holds the path down to the smallest value, with that smallest node on top. Using an explicit stack rather than recursion is what makes early exit clean — you simply stop looping.
Pop to get the next smallest value
Popping the stack yields the next value in ascending order. Increment a counter on each pop. When the counter reaches k, the value just popped is the k-th smallest — return it immediately without touching the rest of the tree.
After popping, descend the right subtree's left spine
Once a node is popped, its left side and itself are done, so the next values come from its right subtree. Move to node.right and push its left spine exactly as in step two. This alternation of pop-then-descend is what keeps the traversal in sorted order.
Mirror everything for the k-th largest
Run the same machine with every direction reversed: push the right spine, and after popping descend into node.left. Values now arrive in descending order, so the k-th pop is the k-th largest. The code is a copy with left and right swapped, which is worth writing out once rather than trying to hold in your head.
Use the node count as a shortcut when you have it
If n is already known, the k-th largest equals the (n − k + 1)-th smallest, so a single forward traversal answers both queries. Only take this route when n is cached — counting the nodes first costs a full O(n) pass and defeats the early stopping.
Cost of the two traversals
Each traversal descends at most the height of the tree and then pops k nodes, giving O(h + k) time and O(h) space for the stack. On a balanced BST with small k that is close to O(log n), a large improvement over flattening the tree, which is O(n) in both time and space regardless of k.
Kth Smallest and Largest in BST solution in Python | C++ | Java
2 from the left gives 8. A real implementation stops the traversal here rather than materialising the whole list.2th largest is the 2th element counting from the right, which sits at index n − k = 3 — 20. A reverse inorder (right, node, left) reaches it directly without materialising the list.1 from the left gives 2. A real implementation stops the traversal here rather than materialising the whole list.1th largest is the 1th element counting from the right, which sits at index n − k = 4 — 6. A reverse inorder (right, node, left) reaches it directly without materialising the list.3 from the left gives 7. A real implementation stops the traversal here rather than materialising the whole list.3th largest is the 3th element counting from the right, which sits at index n − k = 2 — 7. A reverse inorder (right, node, left) reaches it directly without materialising the list.Common pitfalls
Sorting all values to pick both
vals = sorted(inorder(root)) return vals[k-1], vals[-k]
inorder(root, False, [0], small) inorder(root, True, [0], large)
A BST is already ordered — re-sorting throws that away and costs O(n log n) plus O(n) space. Each traversal can stop as soon as it has counted k nodes.
Not stopping once the answer is found
def inorder(node, ...):
inorder(node.left, ...)
count[0] += 1
if count[0] == k: out.append(node.val)
inorder(node.right, ...)if not node or out: return ... if count[0] == k: out.append(node.val); return
Without the early exit the traversal continues past the target and the counter keeps advancing, so a later node can be appended too. Checking out at the top prunes every remaining branch.
Passing the counter as a plain integer
def inorder(node, count):
count += 1def inorder(node, reverse, count, out):
count[0] += 1Integers are immutable in Python, so count += 1 rebinds a local and the increment is lost when the frame returns. The count must be shared across the whole traversal — a one-element list (or a class attribute) provides that.
Edge cases
Smallest = leftmost node, largest = rightmost.
Traversal exhausts → report not found.