Mode(s) in a BST

Find Mode(s) in a BST asks for the most frequently occurring value(s) in a binary search tree that allows duplicates. The trick is to lean on a property the tree hands you for free: an inorder traversal visits values in sorted order, so identical values always land next to each other.

The slow way first

The obvious approach: walk the whole tree, drop every value into a hash map of counts, find the maximum count, then collect every value that hits it. That works and is O(n) time — but it also uses O(n) extra space for the map, and the problem famously asks you to do it without that extra bookkeeping.

The question to ask: can the tree's own structure tell me when equal values are grouped together, so I never need a map?

The idea: count runs during an inorder walk

In a BST, an inorder traversal (left subtree, node, right subtree) yields values in non-decreasing order. With duplicates allowed, that means all copies of a value arrive back-to-back as one run. So we only ever need to track the current run and the best run seen so far.

The key insight: because equal values are adjacent, a single counter is enough. When a run beats the record we reset the answer to that value; when it merely ties, we append it.

Walk through it

Step through the animation. The inorder order is 1, 1, 2, 2, 2, 3. The cur label shows the current value and its run length; the max count label shows the record and the modes so far. Watch 2 climb: it ties 1 at count 2 (so modes briefly become [1, 2]), then its third copy pushes the run to 3, beating the record and resetting the answer to [2].

Pseudocode

max_count = 0
cur_val = none, cur_count = 0
modes = empty list
 
for each value v in inorder(root):     # sorted order
    if v == cur_val:
        cur_count += 1                 # extend the run
    else:
        cur_val = v, cur_count = 1     # start a new run
    if cur_count > max_count:
        max_count = cur_count
        modes = [v]                    # new champion
    else if cur_count == max_count:
        modes.append(v)                # tie -> keep both
 
return modes

The Python solution

def find_mode(root):
    modes, max_count = [], 0
    cur_val, cur_count = None, 0
 
    def visit(val):
        nonlocal cur_val, cur_count, max_count, modes
        if val == cur_val:
            cur_count += 1
        else:
            cur_val, cur_count = val, 1
        if cur_count > max_count:
            max_count = cur_count
            modes = [val]
        elif cur_count == max_count:
            modes.append(val)
 
    inorder(root, visit)
    return modes

• cur_val / cur_count track the value of the current run and how long it is.
• visit is called once per node in inorder order, so values arrive sorted.
• If the incoming value matches the run, we extend it; otherwise we begin a fresh run of length 1.
• Lines 11 to 15 are the heart: a run that beats max_count resets modes to just that value; a run that ties max_count appends the value, so ties are preserved.
• inorder(root, visit) is any standard left-node-right traversal that feeds each value to visit.

Complexity

We touch every node once for O(n) time, and the only extra space is the traversal itself — O(h) for the recursion stack (where h is the tree height), with no counting map. That is the whole point: the BST ordering replaces the map.

When this pattern shows up

Practice