Find Mode in Binary Search Tree

Find Mode in Binary Search Tree

What is this problem about?

The Find Mode in Binary Search Tree interview question asks you to find the most frequently occurring value(s) in a BST. If there are multiple modes, return all of them. This Find Mode in Binary Search Tree coding problem usually comes with a "Hard" follow-up constraint: can you solve it without using extra space (ignoring the recursion stack)?

Why is this asked in interviews?

Companies like Meta and Amazon use this to test your understanding of Tree interview patterns, specifically the relationship between a BST and an In-order traversal. It evaluations whether you know that an in-order traversal of a BST yields elements in non-decreasing order, which allows you to treat the tree like a sorted array.

Algorithmic pattern used

This problem uses In-order Traversal (Recursive or Iterative).

1. Property: Because it's a BST, identical values will appear consecutively during an in-order traversal.
2. Two-Pass Approach:
   • Pass 1: Traverse the tree to find the maximum frequency of any value.
   • Pass 2: Traverse again to collect all values that achieve that frequency.
3. One-Pass (Optimized): Maintain current_val, current_count, max_count, and a result list. As you traverse, if the current_count exceeds max_count, clear the list and update max_count.

Example explanation

BST: 1 is root, 2 is right child, 2 is left child of that 2.

1. In-order visit: 1, 2, 2.
2. Count '1': freq 1. max_freq = 1. Result: [1].
3. Count '2': freq 2. 2 > max_freq. Update max_freq = 2. Result: [2]. Final Result: [2].

Common mistakes candidates make

• Using a Map: Using a Hash Map to store frequencies uses $O(N)$ space, violating the follow-up constraint.
• Incorrect Traversal: Using Pre-order or Post-order, which doesn't visit identical values consecutively.
• Initialization: Forgetting to handle the first element correctly when starting the count logic.

Interview preparation tip

Always remember: In-order = Sorted for BSTs. If a problem on a BST is similar to a problem on a sorted array, the solution almost certainly involves an in-order traversal.