The O(n) Club: BST Mode Madness — Why HashMaps Are Out, and In-Order Is In

The O(n) Club: BST Mode Madness — Why HashMaps Are Out, and In-Order Is In

⚡ TL;DR

Your task: Find the value(s) with the highest frequency (the “modes”) in a BST—yes, the kind that allows duplicates. You could count with a HashMap (yawn, welcome to O(n) space), or you can be a traversal wizard and sweep through in order, using just a few variables. (There’s your O(1) space, unless you count recursion—don’t @ me.) Here’s a kludgy approach for comparison:

// Java brute-force (just say no flatMap):
public int[] findMode(TreeNode root) {
    Map<integer integer> freq = new HashMap<>();
    traverse(root, freq);
    int max = Collections.max(freq.values());
    return freq.entrySet().stream()
        .filter(e -> e.getValue() == max)
        .mapToInt(Map.Entry::getKey)
        .toArray();
}
private void traverse(TreeNode node, Map<integer integer> freq) {
    if (node == null) return;
    freq.put(node.val, freq.getOrDefault(node.val, 0) + 1);
    traverse(node.left, freq);
    traverse(node.right, freq);
}
</integer></integer>

🧠 How Devs Usually Mess This Up

Classic misplays include:

• Assuming everything is unique. BSTs with ≤ instead of < mean you might see the same value everywhere. Don’t treat this like a set—it’s more like a support group for numbers with identical needs.
• HashMap everywhere! You could, sure, but you’ll use a lot more memory just to reinvent what in-order already gives you: sorted order and grouped duplicates.
• Forgetting about ties. Multiple modes are possible, so return everyone with the most votes or risk your output looking, well…awkward.
• Mixing up mode and median. The tree’s structure doesn’t mean you get the middle value for free—this is not ‘Find the Middle Kid in the Family.’ Mode’s about the repeat offenders.

🔍 What’s Actually Going On

Picture the BST as a conga line—doing an in-order traversal means everyone lines up by value, duplicates sticking together like clingy relatives. The recipe: Count each streak as you traverse. If your streak beats the record, update the max. Do this with almost zero extra memory. That’s it—no fancy grimoire required.

Two passes is all you need:

• First pass: Count the frequency of each conga cluster; keep the max.
• Second pass: Invite all numbers that hit that top count to your mode party.

Result: You elegantly sidestep hashmap bloat and earn the approval of the algorithm elders (and interviewers who care about O(1) space).

🛠️ PseudoCode

• State keeps you honest: Use variables for previous value (prev), current streak (count), highest count (maxCount), and—only when you must—an array/list to collect the winning value(s).

  // State
  Integer prev = null;
  int count = 0;
  int maxCount = 0;
  List<Integer> modes;

• Traversal 1, set the record:

  // Traverse left
  // If node.val == prev: count++
  // else: count = 1
  // If count > maxCount: maxCount = count
  // prev = node.val
  // Traverse right

• Traversal 2, collect the winners: Reset except maxCount.

  // Traverse again
  // Same logic, but if count == maxCount, add node.val to modes list

• Convert modes list to int[] and party on. You did it, with no HashMap hangover.

💻 The Code

// Java: O(1) extra space (excluding call stack)
class Solution {
    private Integer prev = null;
    private int count = 0;
    private int maxCount = 0;
    private List<Integer> modes;
     public int[] findMode(TreeNode root) {
        modes = new ArrayList<>();
        // Pass 1: Get max count
        inOrder(root, false);
        // Reset for pass 2
        prev = null;
        count = 0;
        // Pass 2: Collect all modes
        inOrder(root, true);
        return modes.stream().mapToInt(i -> i).toArray();
    }
     private void inOrder(TreeNode node, boolean collect) {
        if (node == null) return;
        inOrder(node.left, collect);
        if (prev != null && node.val == prev) {
            count++;
        } else {
            count = 1;
        }
        if (!collect) {
            maxCount = Math.max(maxCount, count);
        } else if (count == maxCount) {
            modes.add(node.val);
        }
        prev = node.val;
        inOrder(node.right, collect);
    }
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Tree is null? Return an empty array, don’t return null unless you want existential questions in your inbox.
• Multiple modes. If there’s a tie, serve all the winners. Don’t make your method play favorites.
• Result array counts as output space, not “extra” space. You don’t have telepathy, sadly. It’s fine the list is O(k).
• Time/Space: Each pass is O(n). Space: If you ignore the result array (and your stack), O(1) extra. Easy math for once.

🧠 Interviewer Brain-Tattoo

“Just because you can HashMap doesn’t mean you should. Let the BST do the counting—sorted order is a gift, not a suggestion.”