On this page
Description
A BST keeps its values in order, but no node knows its own rank, that is, whether it's the 3rd smallest or the 300th. Inorder traversal visits the values in ascending order, so a node's rank is how many values came before it in inorder. This skill covers three ways to answer "what's the kth smallest (or largest)?": build the whole sorted list, count as you walk and stop at k, or store subtree sizes so that any rank takes one walk down from the root.
We'll go from simple to more technical:
- The pattern: the full inorder list, indexed from either end.
- A second flavor: count inorder visits and stop at k.
- Where rank queries show up (top-k, LIMIT, percentiles).
- What breaks it: counting at the wrong moment, off-by-one indices, not stopping.
The approach
Java
int[] kthSmallestAndLargest(TreeNode root, int k) {
List<Integer> inorder = new ArrayList<>();
traverse(root, inorder); // fills the list in ascending order
int n = inorder.size();
return new int[]{ inorder.get(k - 1), inorder.get(n - k) };
}
Python
def kth_smallest_and_largest(root: TreeNode, k: int) -> list[int]:
inorder = []
traverse(root, inorder) # fills the list in ascending order
n = len(inorder)
return [inorder[k - 1], inorder[n - k]] # inorder[-k] is the same kth largest
Once the whole inorder list exists, both ends are one index away: the kth smallest is at index k - 1, the kth largest at index n - k (0-indexed). That costs O(n) time and space to build - worth it when many rank queries hit the same unchanged tree, wasteful for a single one.
A second flavor: stop at the kth visit
For one query, count as you visit and stop as soon as the count reaches k:
Java
int count = 0, answer;
void kthSmallest(TreeNode node, int k) {
if (node == null || count >= k) return; // already found - stop exploring
kthSmallest(node.left, k);
count++; // this is the node's inorder VISIT
if (count == k) { answer = node.val; return; }
kthSmallest(node.right, k);
}
Python
def kth_smallest(root: TreeNode, k: int) -> int:
count, answer = 0, None
def visit(node: TreeNode | None) -> None:
nonlocal count, answer
if node is None or count >= k:
return # already found - stop exploring
visit(node.left)
count += 1 # this is the node's inorder VISIT
if count == k:
answer = node.val
return
visit(node.right)
visit(root)
return answer
The walk goes down the left spine (O(h)) and then visits exactly k nodes before stopping - O(h + k) time, O(h) space, no list. The kth largest is the same walk mirrored: reverse inorder (right subtree, node, left subtree) visits values in descending order, so its kth visit is the kth largest - no need to know n first.
The one place to get wrong is where count++ goes. It has to come after the left subtree - that's the moment a node is visited in inorder. Counting on entry (before recursing left) counts nodes in preorder, which has nothing to do with rank.
Where you'll see it
"Top k" and "kth ranked" queries - the 10 cheapest listings, the 3rd-highest bid, the median response time - are rank queries over ordered data. Walking in from the correct end and stopping after k is how an ordered index answers ORDER BY price LIMIT 10 without reading the rest of the table.
Which tool for which job?
| You need | Use |
|---|---|
| One rank query, small k | count inorder visits and stop at k: O(h + k) |
| The kth largest | reverse inorder (right, node, left), stop at k |
| Many queries on a tree that doesn't change | build the inorder list once, index k - 1 or n - k |
| Many queries on a tree that changes | store subtree sizes: O(h) per query |
| Python, sorted keys with rank access | sortedcontainers.SortedList (s[k - 1]) |
Common mistakes
| Mistake | What happens | Do this instead |
|---|---|---|
| Counting on entry, before the left subtree | counts preorder: k = 1 returns the root | count after the left subtree |
n - k - 1 or n - k + 1 for the kth largest | off by one | kth smallest k - 1, kth largest n - k |
| No early stop | O(n) for an O(h + k) question | return once the count reaches k |
| Rebuilding the list per query | O(n) every time | build once, or store subtree sizes |
headSet(x).size() in Java as a rank | walks the whole view: O(rank) | a size-augmented tree |
Check yourself
Try to answer before opening each one - recalling beats re-reading.
1. In [5, 3, 8, 2, 4, 7, 9], a kth-smallest walk increments its counter on entry, before recursing left. What does it return for k = 1 and k = 3?
Show answer
5 and 2 - the 1st and 3rd nodes in preorder (5, 3, 2, ...), not in sorted order. The correct answers are 2 and 4. A node's inorder visit happens after its left subtree is done, so that's where the count belongs.
2. How do you find the kth largest without knowing how many nodes there are?
Show answer
Walk in reverse inorder - right subtree, node, left subtree - which visits values in descending order, and stop at the kth visit. The n - k index formula needs n; the mirrored walk doesn't.
3. A tree changes constantly and must answer rank queries fast. What would you store, and what does it buy?
Show answer
The size of each node's subtree. At each node, compare k with the left subtree's size plus one to decide whether the answer is here, to the left, or to the right (with k reduced) - one O(h) path per query. Inserts and deletes update the sizes along their own path, so the extra cost per update is also O(h).
Key takeaways
- Inorder visits a BST in ascending order, so rank is just the count of inorder visits.
- A full inorder list costs O(n) once and then answers any rank in O(1): kth smallest at
k - 1, kth largest atn - k. - For a single query, count as you visit and stop at k: O(h + k). Reverse inorder gives the kth largest the same way.
- Count at the visit - after the left subtree - not on entry, or you're counting preorder.
- For frequent queries on a changing tree, store subtree sizes: O(h) per query.