Find Mode in Binary Search Tree: Inorder Traversal Pattern

Given the root of a binary search tree with duplicates, you need to find all the mode(s), meaning the most frequently occurring element(s). This is LeetCode 501: Find Mode in Binary Search Tree, an easy problem that tests whether you understand the fundamental property of BSTs: inorder traversal produces sorted output.

The problem

Given a BST where each node's left subtree contains only nodes with values less than or equal to the node's value, and each node's right subtree contains only values greater than or equal to the node's value, return all the modes. If the tree has multiple modes, return them all.

Example: given root = [1, null, 2, 2], the output is [2]. The value 2 appears twice while 1 appears once, so 2 is the mode.

The brute force

The most direct approach is to traverse the entire tree (any order works), count every value in a hash map, then scan the map for the maximum frequency.

def find_mode(root):
    if not root:
        return []

    counts = {}

    def dfs(node):
        if not node:
            return
        counts[node.val] = counts.get(node.val, 0) + 1
        dfs(node.left)
        dfs(node.right)

    dfs(root)
    max_count = max(counts.values())
    return [val for val, cnt in counts.items() if cnt == max_count]

This works, but it uses O(n) extra space for the hash map and completely ignores the fact that the input is a BST. You could use this same approach on any tree. When you see a BST in a problem statement, that is almost always a hint to use the sorted property.

The key insight

An inorder traversal of a BST visits nodes in sorted (non-decreasing) order. That means all duplicate values will appear consecutively. You do not need a hash map to count frequencies. Instead, you can track three things as you traverse:

1. current count for the value you are currently seeing
2. max count seen so far
3. modes list containing all values that have reached the current max count

When you visit a node during inorder traversal, if its value matches the previous value, increment the current count. If it is a new value, reset the count to 1. Then compare the current count against the max count. If it exceeds the max, you have found a new best, so clear the modes list and add this value. If it ties the max, add this value to the list.

This approach uses O(1) extra space beyond the recursion stack, which is exactly what the LeetCode follow-up asks for.

Step-by-step walkthrough

Let's trace the inorder approach on a BST where every value appears twice. The tree contains nodes [4, 2, 6, 2, 4, null, 6], giving an inorder sequence of [2, 2, 4, 4, 6, 6].

Notice how the algorithm never looks backward. It processes each node exactly once during the inorder traversal, comparing only against the immediately previous value. Because the BST property guarantees sorted order, duplicates are always adjacent.

The code

def find_mode(root):
    modes = []
    max_count = 0
    current_count = 0
    current_val = None

    def inorder(node):
        nonlocal modes, max_count, current_count, current_val
        if not node:
            return
        inorder(node.left)
        if node.val == current_val:
            current_count += 1
        else:
            current_val = node.val
            current_count = 1
        if current_count > max_count:
            max_count = current_count
            modes = [current_val]
        elif current_count == max_count:
            modes.append(current_val)
        inorder(node.right)

    inorder(root)
    return modes

The function uses nonlocal to modify the tracking variables from within the nested inorder helper. The left recursive call happens first (inorder traversal), then we process the current node, then the right recursive call. The processing logic is the three-way comparison: same value increments count, new value resets count, and then we check if count beats or ties the max.

Complexity analysis

Both approaches visit every node once, so time is O(n). The hash map approach uses O(n) space for the map. The inorder approach uses O(1) extra space for tracking variables, but the recursion stack adds O(h) space where h is the height of the tree. In the worst case (a completely skewed tree), h = n. For a balanced tree, the stack depth is O(log n).

Building blocks

The reusable pattern here is: inorder traversal of a BST produces sorted values. Once you have sorted values, counting adjacent duplicates becomes trivial. This same property powers several other BST problems:

• Validate BST uses inorder to check that values are strictly increasing.
• Kth Smallest Element in a BST uses inorder to find the k-th value in sorted order.
• Convert BST to Greater Tree uses reverse inorder (right, root, left) to accumulate sums.

Any time you need to reason about the relative ordering of values in a BST, think inorder traversal first.

Edge cases

• Single node: the only value is the mode. Count is 1, max count is 1, modes = [root.val].
• All nodes have the same value: every node increments the count. The single value is the mode with count = n.
• No duplicates (every value is unique): every value has count 1, so every value is a mode. The output is all node values.
• Empty tree: return an empty list. The inorder function never recurses, and the modes list stays empty.
• Left-skewed or right-skewed tree: the algorithm still works correctly. The recursion stack depth equals n, but the logic is the same.

From understanding to recall

You now understand two approaches to finding modes in a BST. The brute force uses a hash map and works on any tree. The optimized approach exploits the BST inorder property to track counts with constant extra space.

The key piece to internalize is the three-variable tracking pattern: current_count, max_count, and modes. When count exceeds max, clear and reset. When count ties max, append. This pattern is not unique to this problem. You will see it anywhere you need to find the most frequent element in a sorted or streaming sequence.

Spaced repetition helps you move from "I understand the idea" to "I can write it in five minutes." After a few rounds of recalling the inorder skeleton plus the counting logic, the whole solution becomes automatic. You stop thinking about which variable to update when and just write it.

Related posts

• Binary Tree Inorder Traversal - the inorder traversal pattern
• Validate Binary Search Tree - another BST inorder property
• Kth Smallest Element in a BST - BST order statistics

CodeBricks breaks problems like this into their underlying patterns and drills them independently. Instead of solving random tree problems and hoping the inorder property sticks, you practice the pattern directly until it becomes second nature.