Problem Description

You are given the root of a binary search tree (BST) that may contain duplicate values. Your task is to find and return all the mode(s) of the tree. The mode is the value that appears most frequently in the tree.

Key points about the problem:

1. BST Definition: The tree follows BST properties where:

   • The left subtree of any node contains values less than or equal to the node's value
   • The right subtree of any node contains values greater than or equal to the node's value
   • Both subtrees are also valid BSTs

2. Multiple Modes: If multiple values share the highest frequency, return all of them in any order

3. Return Format: Return the result as a list of integers containing all mode values

For example, if you have a BST with values [1, 2, 2, 3, 3] where both 2 and 3 appear twice (the maximum frequency), you would return [2, 3].

The solution leverages the BST property by performing an in-order traversal, which visits nodes in sorted order. During traversal, it tracks:

• cnt: The count of the current value being processed
• prev: The previous value seen (to detect when the value changes)
• mx: The maximum frequency found so far
• ans: The list of mode values

When traversing in sorted order, identical values appear consecutively, making it easy to count frequencies. If a new maximum frequency is found, the answer list is reset with the current value. If the current frequency equals the maximum, the value is added to the existing answer list.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: A binary search tree is a special type of graph where each node has at most two children (left and right), and nodes are connected by edges (parent-child relationships).

Is it a tree?

• Yes: The problem explicitly states we're working with a Binary Search Tree (BST), which is a specialized tree data structure with specific ordering properties.

DFS

• Since we answered "yes" to the tree question, the flowchart leads us directly to DFS (Depth-First Search).

Conclusion: The flowchart suggests using a DFS approach for this problem.

This makes perfect sense for finding modes in a BST because:

1. DFS allows us to traverse the entire tree systematically to visit every node
2. Using in-order DFS traversal on a BST gives us nodes in sorted order (left → root → right)
3. When values are processed in sorted order, duplicate values appear consecutively, making it easy to count frequencies
4. We can track the current count, maximum frequency, and mode values as we traverse

The solution implements this DFS strategy with an in-order traversal that maintains running counts and updates the mode list whenever a new maximum frequency is encountered or matched.

Intuition

The key insight comes from understanding the special property of BSTs: when we traverse a BST using in-order traversal (left → root → right), we visit nodes in sorted order. This is crucial because it transforms our problem into something much simpler.

Think about finding the mode in a sorted array like [1, 2, 2, 3, 3, 3, 4]. We can simply iterate through it once, counting consecutive identical values. When the value changes, we know we've finished counting that particular number. This is much easier than dealing with an unsorted array where we'd need a hash map to track frequencies.

The same principle applies to our BST. By using in-order DFS traversal, we're essentially "flattening" the tree into a sorted sequence. As we traverse:

1. We keep track of the previous value (prev) to know when we encounter a new distinct value
2. We maintain a running count (cnt) that increments when we see the same value again, or resets to 1 when we see a new value
3. We track the maximum frequency (mx) seen so far
4. We maintain our answer list (ans) of mode values

The beauty of this approach is that we only need O(1) extra space (excluding recursion stack) instead of using a hash map to count all frequencies. When we encounter a value with frequency equal to the current maximum, we add it to our answer list. If we find a value with even higher frequency, we clear the answer list and start fresh with this new mode.

This solution elegantly combines the BST property with DFS traversal to solve what could have been a more complex counting problem in a single pass through the tree.

Learn more about Tree, Depth-First Search, Binary Search Tree and Binary Tree patterns.

Solution Approach

The implementation uses an in-order DFS traversal with clever state tracking to find all modes in a single pass through the BST.

Core Algorithm Structure:

The solution defines a nested dfs function that performs in-order traversal:

def dfs(root):
    if root is None:
        return
    dfs(root.left)    # Process left subtree
    # Process current node
    dfs(root.right)   # Process right subtree

State Variables:

Before starting the traversal, we initialize four key variables:

• prev = None: Tracks the previous node's value to detect when values change
• cnt = 0: Counts occurrences of the current value
• mx = 0: Stores the maximum frequency found so far
• ans = []: List to store all mode values

Processing Each Node:

When visiting each node in sorted order, the algorithm:

1. Updates the count:

   cnt = cnt + 1 if prev == root.val else 1

   If the current value equals the previous value, increment the count; otherwise, reset to 1.

2. Handles mode detection:

   if cnt > mx:
       ans = [root.val]
       mx = cnt
   elif cnt == mx:
       ans.append(root.val)

   • If current count exceeds the maximum, we found a new mode with higher frequency. Clear the answer list and add only this value.
   • If current count equals the maximum, this value is also a mode. Add it to the existing modes.

3. Updates previous value:

   prev = root.val

   Store the current value for comparison with the next node.

Why This Works:

The in-order traversal ensures we process values in ascending order. For example, if the BST contains values [1, 2, 2, 3, 3, 3] in sorted order:

• When we see the first 2, cnt becomes 1
• When we see the second 2, cnt becomes 2
• When we see the first 3, we know we're done counting 2s, so cnt resets to 1
• This pattern continues, allowing us to accurately count frequencies

The use of nonlocal keyword allows the nested function to modify the outer function's variables, maintaining state across recursive calls without passing parameters back and forth.

Time and Space Complexity:

• Time: O(n) where n is the number of nodes, as we visit each node exactly once
• Space: O(h) for the recursion stack, where h is the height of the tree

Example Walkthrough

Let's walk through a small example to illustrate how the solution works.

Consider this BST:

      4
     / \
    2   6
   / \   \
  2   3   6

The values in in-order traversal are: [2, 2, 3, 4, 6, 6]

Initial State:

• prev = None, cnt = 0, mx = 0, ans = []

Step-by-step traversal:

1. Visit first 2 (leftmost node)

   • prev = None, so this is our first value
   • cnt = 1 (first occurrence)
   • cnt > mx (1 > 0), so mx = 1, ans = [2]
   • Update: prev = 2

2. Visit second 2

   • prev = 2 equals current value 2
   • cnt = 2 (increment from 1)
   • cnt > mx (2 > 1), so mx = 2, ans = [2] (reset with current value)
   • Update: prev = 2

3. Visit 3

   • prev = 2 ≠ current value 3
   • cnt = 1 (reset for new value)
   • cnt < mx (1 < 2), no changes to ans
   • Update: prev = 3

4. Visit 4 (root)

   • prev = 3 ≠ current value 4
   • cnt = 1 (reset for new value)
   • cnt < mx (1 < 2), no changes to ans
   • Update: prev = 4

5. Visit first 6

   • prev = 4 ≠ current value 6
   • cnt = 1 (reset for new value)
   • cnt < mx (1 < 2), no changes to ans
   • Update: prev = 6

6. Visit second 6

   • prev = 6 equals current value 6
   • cnt = 2 (increment from 1)
   • cnt == mx (2 == 2), so append to ans: ans = [2, 6]
   • Update: prev = 6

Final Result: [2, 6] - both values appear twice, which is the maximum frequency in the tree.

The key insight is that the in-order traversal gives us sorted values, allowing us to count consecutive occurrences efficiently. When a value changes (detected by comparing with prev), we know we've finished counting that particular value and can reset our counter for the new value.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n) where n is the number of nodes in the binary tree. The algorithm performs an in-order traversal of the tree, visiting each node exactly once. The in-order traversal through the recursive DFS function processes every node with constant time operations (comparisons, assignments, and list operations), resulting in linear time complexity.

Space Complexity: O(h) where h is the height of the binary tree, which represents the recursive call stack space. In the worst case of a skewed tree, this would be O(n), while in the best case of a balanced tree, it would be O(log n). Additionally, the algorithm uses O(1) auxiliary space for the variables prev, mx, cnt, and the output list ans could contain at most n elements in the worst case where all nodes have the same value. Therefore, the overall space complexity is O(h) + O(k) where k is the number of modes, but since k ≤ n, the space complexity can be expressed as O(h) for the recursion stack plus O(n) for the output in the worst case.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting to Handle the First Node Properly

A common mistake is not properly initializing or handling the comparison when previous_value is None (when processing the very first node in the traversal).

Incorrect approach:

# This could cause issues if not handled properly
if previous_value == node.val:  # When previous_value is None, this is always False
    current_count += 1
else:
    current_count = 1

Why it's actually fine in this solution: The current implementation cleverly handles this because when previous_value is None, the comparison None == node.val is always False, so current_count correctly gets set to 1 for the first node. However, this implicit behavior can be confusing.

More explicit solution:

if previous_value is not None and previous_value == node.val:
    current_count += 1
else:
    current_count = 1

2. Using Global Variables Instead of Nonlocal

Developers might try to use global variables or instance variables instead of the nonlocal keyword, leading to scope issues.

Problematic approach:

class Solution:
    def findMode(self, root):
        self.previous_value = None  # Instance variable
        self.current_count = 0
        # ... rest of the code
      
        def inorder_traversal(node):
            # Forgetting to use self.previous_value consistently
            if previous_value == node.val:  # NameError!
                current_count += 1

Solution: Stick with the nonlocal approach for cleaner code, or consistently use self. prefix for all instance variables.

3. Incorrect Mode List Reset Logic

A subtle bug can occur if the mode list isn't properly reset when finding a new maximum frequency.

Incorrect approach:

if current_count > max_frequency:
    mode_list.append(node.val)  # Wrong! Should reset the list
    max_frequency = current_count
elif current_count == max_frequency:
    mode_list.append(node.val)

This would keep values from lower frequencies in the result.

Correct approach:

if current_count > max_frequency:
    mode_list = [node.val]  # Reset the list with only the new mode
    max_frequency = current_count
elif current_count == max_frequency:
    mode_list.append(node.val)

4. Attempting Two-Pass Solution When One Pass Suffices

Some developers might overcomplicate by first traversing to find the maximum frequency, then traversing again to collect all values with that frequency.

Overcomplicated approach:

def findMode(self, root):
    # First pass: find maximum frequency
    frequency_map = {}
    def count_frequencies(node):
        if not node:
            return
        frequency_map[node.val] = frequency_map.get(node.val, 0) + 1
        count_frequencies(node.left)
        count_frequencies(node.right)
  
    count_frequencies(root)
    max_freq = max(frequency_map.values())
  
    # Second pass: collect modes
    return [val for val, freq in frequency_map.items() if freq == max_freq]

While this works, it uses O(n) extra space for the hash map and doesn't leverage the BST property. The single-pass in-order traversal is more elegant and space-efficient.

5. Not Leveraging BST Properties

Using a generic tree traversal without considering that in-order traversal of a BST gives sorted values.

Less optimal approach:

def findMode(self, root):
    frequency_map = {}
  
    def traverse(node):
        if not node:
            return
        # Any order traversal, then using a hash map
        frequency_map[node.val] = frequency_map.get(node.val, 0) + 1
        traverse(node.left)
        traverse(node.right)
  
    traverse(root)
    # Find max frequency and return modes

This misses the optimization opportunity that consecutive equal values in in-order traversal can be counted without extra space for frequency storage.