Find Mode in Binary Search Tree

LeetCode 501: Find Mode in Binary Search Tree Solution & Explanation

Problem Overview

TL;DR: By utilizing the sorted property of a Binary Search Tree (BST), we perform an inorder traversal to process nodes as a sorted sequence, allowing us to count frequencies and identify modes in a single pass without using a hash map.

The LeetCode 501 problem, "Find Mode in Binary Search Tree," asks us to identify the element(s) that appear most frequently in a BST. Unlike a standard binary tree, the BST structure guarantees a specific ordering of keys. If multiple elements share the same maximum frequency, we must return all of them. The solution should ideally handle the "Follow up" constraint: solving it without using extra space for frequency counting.

Brute Force Approach for Find Mode in Binary Search Tree

The most intuitive way to solve this problem is to treat the BST as a generic Binary Tree, ignoring its sorted property. We can traverse the entire tree and store the frequency of every element in a Hash Map.

Naive Algorithm Steps

1. Initialize an empty Hash Map (or Dictionary) to store value -> count.
2. Traverse the tree using any method (Preorder, Inorder, or Postorder).
3. For every node visited, increment its count in the Hash Map.
4. Iterate through the Hash Map to find the maximum frequency (max_freq).
5. Iterate through the Hash Map again to collect all keys where count == max_freq.

Pseudo-code

function findMode(root):
    map = new HashMap()
    
    function traverse(node):
        if node is null return
        map[node.val]++
        traverse(node.left)
        traverse(node.right)
    
    traverse(root)
    
    max_freq = 0
    for count in map.values():
        max_freq = max(max_freq, count)
        
    result = []
    for key in map.keys():
        if map[key] == max_freq:
            result.add(key)
            
    return result

Analysis

• Time Complexity: $O(N)$, where $N$ is the number of nodes. We visit every node once and iterate through the map.
• Space Complexity: $O(N)$. In the worst case (all unique values), the map stores $N$ entries.
• Why it fails: While this solution is correct, it fails to utilize the BST property. The problem includes a follow-up asking for $O(1)$ extra space (excluding recursion stack). The brute force approach relies heavily on $O(N)$ auxiliary space for the map, making it suboptimal for this specific constraint.

Algorithm Strategy: Tree DFS - Recursive Inorder Traversal

The strategy relies on a stateful Inorder Traversal. Since the recursion stack handles the traversal order, we manage the logic for frequency counting within the visitation step.

1. Global Variables (or Class Members):

   • prev: Stores the value of the previously visited node. Initialized to null/none.
   • currCount: Tracks the frequency of the current value being processed.
   • maxCount: Tracks the highest frequency seen so far.
   • result: A list to store the mode(s).

2. Traversal Logic (DFS):

   • Recursively call DFS on the left child.
   • Process Node: Compare root.val with prev. Update currCount. Compare currCount with maxCount to update result. Update prev to root.val.
   • Recursively call DFS on the right child.

3. Handling Updates:

   • Crucially, when currCount exceeds maxCount, the result list is cleared because all previously stored modes are no longer the most frequent. The current value becomes the sole new mode.

Execution Flow

1. Initialization: Set maxCount = 0, currCount = 0, prev = null, and result = [].
2. Start Recursion: Call inorder(root).
3. Navigate Left: The function recurses until it hits the leftmost leaf (smallest value).
4. Process Node (e.g., Value A):
   • Check prev. If prev is null or prev != A, reset currCount = 1.
   • If prev == A, increment currCount.
   • Mode Check:
     • Is currCount > maxCount? Update maxCount = currCount. Clear result. Add A.
     • Is currCount == maxCount? Add A to result.
   • Update prev = A.
5. Navigate Right: Recurse to the right child.
6. Repeat: This continues for all nodes. The prev variable acts as the bridge between recursive calls, ensuring we treat the tree as a continuous sorted stream.
7. Return: Finally, return result.

Proof of Correctness

The correctness hinges on the property of BSTs: Inorder Traversal produces a sorted sequence.

• Completeness: The traversal visits every node exactly once.
• Adjacency: Since the sequence is sorted, all instances of a value $X$ appear consecutively. We will never encounter an $X$, then a $Y$, and then another $X$.
• Counting: By resetting the counter whenever the value changes, currCount accurately reflects the total frequency of the contiguous block of identical values.
• Maximization: By dynamically updating result whenever currCount matches or exceeds maxCount, the algorithm guarantees that after the final node is processed, result contains exactly those elements with the global maximum frequency.

Pattern Reuse Notes

The Tree DFS - Recursive Inorder Traversal pattern is fundamental for Binary Search Trees. It allows us to process the tree as a sorted array.

• LeetCode 94: Binary Tree Inorder Traversal: The base pattern itself.
• LeetCode 98: Validate Binary Search Tree: Uses inorder traversal to verify that the sequence is strictly increasing (prev < current).
• LeetCode 173: Binary Search Tree Iterator: Implements a controlled inorder traversal using an explicit stack.
• LeetCode 230: Kth Smallest Element in a BST: Stops the inorder traversal early once the $k$-th element is reached.

Reference Implementation

C++ Solution for LeetCode 501

1class Solution {
2private:
3    int maxCount = 0;
4    int currCount = 0;
5    TreeNode* prev = nullptr;
6    vector<int> result;
7
8    void inorder(TreeNode* node) {
9        if (!node) return;
10
11        // 1. Traverse Left
12        inorder(node->left);
13
14        // 2. Process Current Node
15        if (prev && prev->val == node->val) {
16            currCount++;
17        } else {
18            currCount = 1;
19        }
20
21        if (currCount > maxCount) {
22            maxCount = currCount;
23            result.clear();
24            result.push_back(node->val);
25        } else if (currCount == maxCount) {
26            result.push_back(node->val);
27        }
28
29        prev = node;
30
31        // 3. Traverse Right
32        inorder(node->right);
33    }
34
35public:
36    vector<int> findMode(TreeNode* root) {
37        inorder(root);
38        return result;
39    }
40};

Java Solution for LeetCode 501

1class Solution {
2    private Integer prev = null;
3    private int currCount = 0;
4    private int maxCount = 0;
5    private List<Integer> result;
6
7    public int[] findMode(TreeNode root) {
8        result = new ArrayList<>();
9        inorder(root);
10        
11        // Convert List to int[]
12        int[] modes = new int[result.size()];
13        for (int i = 0; i < result.size(); i++) {
14            modes[i] = result.get(i);
15        }
16        return modes;
17    }
18
19    private void inorder(TreeNode node) {
20        if (node == null) return;
21
22        // 1. Traverse Left
23        inorder(node.left);
24
25        // 2. Process Current Node
26        if (prev != null && prev == node.val) {
27            currCount++;
28        } else {
29            currCount = 1;
30        }
31
32        if (currCount > maxCount) {
33            maxCount = currCount;
34            result.clear();
35            result.add(node.val);
36        } else if (currCount == maxCount) {
37            result.add(node.val);
38        }
39
40        prev = node.val;
41
42        // 3. Traverse Right
43        inorder(node.right);
44    }
45}

Python Solution for LeetCode 501

1class Solution:
2    def findMode(self, root: Optional[TreeNode]) -> List[int]:
3        self.max_count = 0
4        self.curr_count = 0
5        self.prev_val = None
6        self.result = []
7        
8        def inorder(node):
9            if not node:
10                return
11            
12            # 1. Traverse Left
13            inorder(node.left)
14            
15            # 2. Process Current Node
16            if node.val == self.prev_val:
17                self.curr_count += 1
18            else:
19                self.curr_count = 1
20            
21            if self.curr_count > self.max_count:
22                self.max_count = self.curr_count
23                self.result = [node.val] # Clear and add
24            elif self.curr_count == self.max_count:
25                self.result.append(node.val)
26                
27            self.prev_val = node.val
28            
29            # 3. Traverse Right
30            inorder(node.right)
31            
32        inorder(root)
33        return self.result