Kth Largest in a BST

Kth Largest Element in a BST turns one fact about binary search trees into a tiny, elegant traversal. The trick: a BST already holds its values in sorted order if you walk it the right way — so finding the kth largest is just counting nodes as you visit them in descending order.

The slow way first

The obvious idea: collect every value into a list, sort it, and pick the kth from the end. That works, but sorting costs O(n log n) and throws away the structure the BST already gives you for free.

The question to ask: what order does a BST visit its values in? A normal in-order walk — left, root, right — visits values in ascending order. We want descending. So we just mirror the walk.

The idea: walk it right, root, left

A reverse in-order traversal — right subtree, then the node, then left subtree — visits the values from largest to smallest. Keep a counter k. Every time we visit a node, decrement k. The moment k hits 0, the node we are standing on is the answer, and we can stop immediately.

The key insight: because we go right before touching the node, the nodes are visited strictly largest-first. So the kth node visited is exactly the kth largest — no sorting, and we stop as soon as we find it.

Walk through it

Step through the animation with k = 2. From root 4 we dive right into 6, then right again into 7 — the largest value, visited first (k: 2 → 1). 7 has no children to its left, so we return up to 6, visit it (k: 1 → 0), and stop. The 2nd largest value is 6.

Pseudocode

k counter starts at the given k
define visit(node):
    if node is empty: return nothing
    answer = visit(node.right)        # larger values first
    if answer was found: return it
    k = k - 1                         # visit this node
    if k == 0: return node.value      # this is the kth largest
    return visit(node.left)           # smaller values
return visit(root)

The Python solution

def kth_largest(root, k):
    self.k = k
    def visit(node):
        if not node:
            return None
        right = visit(node.right)
        if right is not None:
            return right
        self.k -= 1
        if self.k == 0:
            return node.val
        return visit(node.left)
    return visit(root)

• self.k holds the live countdown so every recursive call shares one counter.
• visit(node.right) recurses into the right subtree first — that is what makes the order descending.
• If that right call already found the answer, we pass it straight back up and never touch the rest.
• self.k -= 1 happens when we actually visit this node, after its right subtree is fully done.
• if self.k == 0 is the stopping condition — the current node.val is the kth largest, returned immediately.
• Only if we have not found it do we descend left into the smaller values.

Complexity

We visit at most k nodes plus the height h it takes to reach the largest value, so the work is O(h + k) — and in the worst case (a skewed tree, or large k) that is O(n). The extra space is the recursion stack, O(h), which is O(log n) for a balanced tree.

When this pattern shows up

Practice