Find Mode in Binary Search Tree

easy tree bst dfs

Problem

Given the root of a BST that may contain duplicates, return every value that occurs most frequently. Try to use O(1) extra space (not counting recursion stack).

Inputroot = [1,null,2,2]

Output[2]

2 appears twice, 1 once. Mode is 2.

tree (level-order, "null" for empty)

def find_mode(root):
    modes, max_count, count, prev = [], 0, 0, None
    def inorder(node):
        nonlocal max_count, count, prev
        if not node: return
        inorder(node.left)
        count = count + 1 if node.val == prev else 1
        if count > max_count:
            max_count, modes[:] = count, [node.val]
        elif count == max_count:
            modes.append(node.val)
        prev = node.val
        inorder(node.right)
    inorder(root)
    return modes

function findMode(root) {
  let modes = [], maxCount = 0, count = 0, prev = null;
  function inorder(node) {
    if (!node) return;
    inorder(node.left);
    count = node.val === prev ? count + 1 : 1;
    if (count > maxCount) { maxCount = count; modes = [node.val]; }
    else if (count === maxCount) modes.push(node.val);
    prev = node.val;
    inorder(node.right);
  }
  inorder(root);
  return modes;
}

class Solution {
    List<Integer> modes = new ArrayList<>();
    int maxCount = 0, count = 0;
    Integer prev = null;
    public int[] findMode(TreeNode root) {
        inorder(root);
        int[] r = new int[modes.size()];
        for (int i = 0; i < r.length; i++) r[i] = modes.get(i);
        return r;
    }
    void inorder(TreeNode n) {
        if (n == null) return;
        inorder(n.left);
        count = (prev != null && n.val == prev) ? count + 1 : 1;
        if (count > maxCount) { maxCount = count; modes.clear(); modes.add(n.val); }
        else if (count == maxCount) modes.add(n.val);
        prev = n.val;
        inorder(n.right);
    }
}

class Solution {
    vector<int> modes;
    int maxCount = 0, count = 0;
    int prev = INT_MIN; bool first = true;
public:
    vector<int> findMode(TreeNode* root) { inorder(root); return modes; }
    void inorder(TreeNode* n) {
        if (!n) return;
        inorder(n->left);
        count = (!first && n->val == prev) ? count + 1 : 1;
        first = false;
        if (count > maxCount) { maxCount = count; modes = { n->val }; }
        else if (count == maxCount) modes.push_back(n->val);
        prev = n->val;
        inorder(n->right);
    }
};

Explanation

The big idea is to lean on a special property of a BST: an inorder traversal (left, node, right) visits the values in sorted order. That means any duplicates land right next to each other, so we can count them without a hash map.

As we walk in sorted order, we track the current run length in count. Each time we visit a node, if its value equals the prev value we just saw, the run grows by one; otherwise the run restarts at 1.

We compare each run against the best seen so far in max_count. If count > max_count, this value is the new sole leader, so we reset modes to just [node.val]. If count == max_count, it ties the leader, so we append it to modes.

Example: root = [1,null,2,2]. Inorder gives 1, 2, 2. At 1, count is 1 (new max), modes [1]. At the first 2, count is 1 again, ties, modes [1,2]. At the second 2, count becomes 2, a new max, so modes resets to [2].

Because we only keep a few counters and never store the full list, this runs in O(n) time and uses O(1) extra space beyond the recursion stack.

Time: O(n) Space: O(h) recursion + answer