Find Mode in BST

Problem

Given the root of a BST that may contain duplicates, return every mode (value that appears most often). The answer may be in any order.

Constraints

• 1 ≤ nodes ≤ 10⁴

Approach — Tree Traversal

This is a Tree Traversal problem. The idea: traverse the tree — DFS recursively, or BFS level by level — and combine the results from each subtree. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: O(n) time.

Solution code

Python

class Solution:
    def findMode(self, root):
        from collections import Counter
        c = Counter()
        def dfs(node):
            if not node:
                return
            c[node.val] += 1
            dfs(node.left); dfs(node.right)
        dfs(root)
        if not c:
            return []
        best = max(c.values())
        return [v for v in sorted(c) if c[v] == best]

Java

import java.util.*;

class Solution {
    public int[] findMode(TreeNode root) {
        Map<Integer,Integer> count = new HashMap<>();
        walk(root, count);
        int best = 0;
        for (int v : count.values()) best = Math.max(best, v);
        List<Integer> modes = new ArrayList<>();
        for (var e : count.entrySet()) if (e.getValue() == best) modes.add(e.getKey());
        int[] out = new int[modes.size()];
        for (int i = 0; i < out.length; i++) out[i] = modes.get(i);
        return out;
    }
    private void walk(TreeNode n, Map<Integer,Integer> c) {
        if (n == null) return;
        c.merge(n.val, 1, Integer::sum);
        walk(n.left, c); walk(n.right, c);
    }
}

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.