Introduction

The median of a binary search tree is the middle value of its nodes in sorted order. Because an in-order traversal of a BST yields values in nondecreasing order, the median problem is really about finding the middle element, or middle two elements, of that traversal without turning the whole tree into a sorted array unless you actually need to.

Why In-Order Traversal Is The Key

A BST has the property that all values in the left subtree are smaller than the node and all values in the right subtree are larger. In-order traversal therefore visits values in sorted order.

1class Node:
2    def __init__(self, value, left=None, right=None):
3        self.value = value
4        self.left = left
5        self.right = right
6
7
8def inorder(node):
9    if node is None:
10        return
11    yield from inorder(node.left)
12    yield node.value
13    yield from inorder(node.right)

Once you know that traversal order is sorted, the median definition becomes straightforward.

Step 1: Count The Nodes

To know which position is the median, first count how many nodes the tree contains.

1def count_nodes(node):
2    if node is None:
3        return 0
4    return 1 + count_nodes(node.left) + count_nodes(node.right)

If the tree has n nodes:

• for odd n, the median is the value at position n // 2
• for even n, the median is the average of positions n // 2 - 1 and n // 2

Those positions are zero-based positions in the sorted order.

Step 2: Walk To The Middle Values

A simple implementation performs a second in-order traversal and stops once the median positions are reached.

1def median_bst(root):
2    n = count_nodes(root)
3    if n == 0:
4        raise ValueError("tree is empty")
5
6    targets = [n // 2] if n % 2 == 1 else [n // 2 - 1, n // 2]
7    found = []
8
9    for index, value in enumerate(inorder(root)):
10        if index in targets:
11            found.append(value)
12        if len(found) == len(targets):
13            break
14
15    if len(found) == 1:
16        return float(found[0])
17    return (found[0] + found[1]) / 2.0

This uses O(n) time overall and O(h) recursion space, where h is the tree height.

Example

1root = Node(
2    5,
3    left=Node(3, Node(1), Node(4)),
4    right=Node(8, Node(7), Node(9)),
5)
6
7print(median_bst(root))

The in-order order is 1, 3, 4, 5, 7, 8, 9, so the median is 5.0.

Can It Be Done In One Traversal

Not cleanly with ordinary recursion unless you already know the node count. That is why the standard approach is:

• one traversal to count nodes
• one traversal to find the middle value or values

This is still O(n) time, which is optimal because in the general case you must inspect the structure enough to know how many nodes exist.

What About Extra Space

A common beginner solution stores the full in-order traversal in a list and then indexes the middle.

1def median_with_list(root):
2    values = list(inorder(root))
3    n = len(values)
4    if n % 2 == 1:
5        return float(values[n // 2])
6    return (values[n // 2 - 1] + values[n // 2]) / 2.0

That is easy to write, but it uses O(n) extra memory. The two-pass streaming approach is usually better when the tree is large.

Morris Traversal Variant

If you need O(1) extra auxiliary space, Morris traversal can walk the BST in sorted order by temporarily rewiring pointers. It is a valid interview follow-up, but it is more complex and easier to get wrong than the standard recursive or stack-based approach.

Unless constant auxiliary space is a hard requirement, the simpler two-pass solution is usually preferable.

Common Pitfalls

The biggest mistake is forgetting that the median is defined in sorted order, not in the tree's structural shape. Another is using zero-based and one-based positions inconsistently, which causes off-by-one errors in even-sized trees. Developers also sometimes average the wrong two middle values for even counts. Finally, if duplicates are allowed in the BST, the in-order traversal still works, but your implementation should not assume all values are distinct.

Summary

• In-order traversal gives BST values in sorted order.
• Count nodes first so you know which position or positions define the median.
• A two-pass solution is simple and still runs in O(n) time.
• Building a full list works, but uses O(n) extra memory.
• Be careful with even-sized trees and position indexing.