Median of a BST

Median of a BST is a classic tree problem that rewards knowing one fact cold: an in-order traversal of a binary search tree visits its values in sorted order. Once you see that, the median is just the middle of a sorted list — and you never have to sort anything.

The slow way first

The obvious idea: traverse the tree, collect every value into a list, sort the list, and pick the middle. That works, but sorting costs O(n log n) and the list costs O(n) extra space — and it throws away the structure we were handed for free.

The question to ask: what does the BST already give me? It gives me sorted order directly. An in-order walk (left subtree, node, right subtree) emits values smallest to largest with no sorting at all.

The idea: count, then walk to the middle

Do it in two passes. First count the nodes to get n, which tells you the rank of the median — for an odd n, that is the (n+1)/2-th value in sorted order. Then do an in-order traversal, keeping a running position counter. The moment the counter hits the target rank, the node you are visiting is the median.

The key insight: we do not build a sorted list. The in-order order plus a counter is enough, and we can stop the walk early the instant the counter reaches the median rank.

Walk through it

Step through the animation. We count first: n = 7, so the target rank is 4. Then the in-order walk visits 1, 3, 4, and on the 4th visit lands on 6 — the root. That equals the target rank, so we stop and return 6.

Pseudocode

n = number of nodes in the tree        # one traversal to count
target = (n + 1) / 2                    # rank of the median (odd n)
pos = 0
in-order traverse the tree:            # left, node, right -> sorted order
    visit left subtree
    pos = pos + 1                       # we are now AT this node in sorted order
    if pos == target:
        return this node's value        # the median
    visit right subtree

The Python solution

def median_of_bst(root):
    def count(node):
        return 0 if node is None else 1 + count(node.left) + count(node.right)
    n = count(root)
    target = (n + 1) // 2
    def inorder(node):
        if node is None:
            return None
        left = inorder(node.left)
        if left is not None:
            return left
        median_of_bst.pos += 1
        if median_of_bst.pos == target:
            return node.val
        return inorder(node.right)
    median_of_bst.pos = 0
    return inorder(root)

• count is a quick recursive node count — n tells us how big the tree is.
• target = (n + 1) // 2 is the rank of the median value in sorted order (for an odd n).
• inorder does the left-node-right walk; recursing left first is what makes the visit order sorted.
• The shared pos counter increments after the left subtree is done — that is the exact moment we are "at" this node in sorted order.
• When pos equals target, the current node is the median, so we return its value and the recursion unwinds without visiting anything more.

Complexity

We spend O(n) time across the count and the partial in-order walk, and only O(h) space for the recursion stack (h is the tree height). No sorted list, no sorting — we lean entirely on the BST ordering.

When this pattern shows up

Practice