# Find Mode in Binary Search Tree
**Difficulty:** EASY
[External](https://leetcode.com/problems/find-mode-in-binary-search-tree)
Canonical: https://scaleengineer.com/dsa/problems/find-mode-in-binary-search-tree
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search)
**Data structures:** Tree, Binary Tree, Binary Search Tree
---
## Problem
Given the `root` of a binary search tree (BST) with duplicates, return _all the [mode(s)](https://en.wikipedia.org/wiki/Mode%5F%28statistics%29) (i.e., the most frequently occurred element) in it_.

If the tree has more than one mode, return them in **any order**.

Assume a BST is defined as follows:

* The left subtree of a node contains only nodes with keys **less than or equal to** the node's key.
* The right subtree of a node contains only nodes with keys **greater than or equal to** the node's key.
* Both the left and right subtrees must also be binary search trees.

**Example 1:**

![](https://assets.glich.co/dsa/find-mode-in-binary-search-tree/image0.jpg) 

**Input:** root = [1,null,2,2]
**Output:** [2]

**Example 2:**

**Input:** root = [0]
**Output:** [0]

**Constraints:**

* The number of nodes in the tree is in the range `[1, 104]`.
* `-105 <= Node.val <= 105`

**Follow up:** Could you do that without using any extra space? (Assume that the implicit stack space incurred due to recursion does not count).

# Approaches
## HashMap Frequency Count
This approach involves traversing the tree and using a hash map to store the frequency of each node's value. After counting all frequencies, we find the maximum frequency and then collect all values that have this frequency. This method is straightforward but does not utilize the properties of a Binary Search Tree.
**Time:** O(N), where N is the number of nodes in the tree. We traverse each node once to populate the map (O(N)), and then iterate through the map (at most N unique entries) to find the max frequency and the modes (O(U)). The total time is O(N). · **Space:** O(U), where U is the number of unique values in the tree. In the worst case, all nodes have unique values, so the space complexity is O(N).
**Pros:** Easy to understand and implement.; Works for any binary tree, not just a BST.
**Cons:** Uses significant extra space for the hash map, which doesn't meet the follow-up constraint.; Doesn't take advantage of the BST property.
### Explanation
The most intuitive way to solve this problem is to count the occurrences of each number. A hash map is a perfect data structure for this. We can traverse the tree using any order (pre-order, in-order, or post-order) and populate a hash map where the key is the node's value and the value is its frequency. After the first traversal populates the map, we perform a second pass over the map's entries to determine the highest frequency. Finally, a third pass over the map collects all the numbers that have this maximum frequency.

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private Map<Integer, Integer> counts = new HashMap<>();

    public int[] findMode(TreeNode root) {
        if (root == null) {
            return new int[0];
        }
        
        traverse(root);
        
        int maxFreq = 0;
        for (int freq : counts.values()) {
            maxFreq = Math.max(maxFreq, freq);
        }
        
        List<Integer> modes = new ArrayList<>();
        for (Map.Entry<Integer, Integer> entry : counts.entrySet()) {
            if (entry.getValue() == maxFreq) {
                modes.add(entry.getKey());
            }
        }
        
        return modes.stream().mapToInt(i->i).toArray();
    }

    private void traverse(TreeNode node) {
        if (node == null) {
            return;
        }
        counts.put(node.val, counts.getOrDefault(node.val, 0) + 1);
        traverse(node.left);
        traverse(node.right);
    }
}
```
### Algorithm
*   Initialize a `HashMap<Integer, Integer>` to store the frequency of each number.
*   Define a traversal function (e.g., DFS or BFS) that takes a node as input.
*   Inside the traversal function, for the current node, update its count in the `counts` map: `counts.put(node.val, counts.getOrDefault(node.val, 0) + 1)`.
*   Recursively call the traversal function for the left and right children.
*   Start the traversal from the `root`.
*   After the traversal is complete, find the maximum frequency (`maxFreq`) among all values in the `counts` map.
*   Initialize an empty list `modes`.
*   Iterate through the `counts` map again. If a key's value (frequency) is equal to `maxFreq`, add the key to the `modes` list.
*   Convert the `modes` list to an integer array and return it.

## Two-Pass In-order Traversal
This approach leverages the property of a BST that an in-order traversal visits nodes in non-decreasing order. This means all occurrences of a value are visited consecutively. We can find the mode by making two passes over the tree. The first pass determines the maximum frequency of any value, and the second pass collects all values that have this maximum frequency.
**Time:** O(N), as it requires two full traversals of the tree (O(N) + O(N)). · **Space:** O(H) for the recursion stack, where H is the height of the tree. This is O(log N) for a balanced tree and O(N) for a skewed tree. It uses O(1) auxiliary space besides the recursion stack and the output list.
**Pros:** Space efficient, meeting the follow-up constraint (O(1) auxiliary space).; Leverages the BST property.
**Cons:** Inefficient due to traversing the tree twice.; More complex to implement correctly compared to the HashMap approach.
### Explanation
To avoid the O(N) space complexity of the HashMap, we can utilize the BST property. An in-order traversal visits nodes in a sorted manner, which groups all identical values together. This allows us to count frequencies without a map.

However, we don't know what the maximum frequency is until we've seen all the numbers. This necessitates a two-pass approach:
1.  **First Pass:** Perform an in-order traversal solely to find the value of the maximum frequency (`maxFreq`). We keep track of the current number's streak (`currentCount`) and update `maxFreq` whenever a longer streak is found.
2.  **Second Pass:** Perform another in-order traversal. This time, we know the `maxFreq`. We again count the streaks of numbers, and if a number's streak count equals `maxFreq`, we add it to our result list.

This method satisfies the follow-up's space constraint but at the cost of traversing the entire tree twice.

```java
class Solution {
    private int currentCount = 0;
    private int maxFreq = 0;
    private Integer prevVal = null;
    private List<Integer> modes = new ArrayList<>();

    public int[] findMode(TreeNode root) {
        // Pass 1: Find the max frequency
        inorderPass1(root);
        
        // Reset for Pass 2
        prevVal = null;
        currentCount = 0;
        
        // Pass 2: Collect the modes
        inorderPass2(root);
        
        return modes.stream().mapToInt(i -> i).toArray();
    }

    private void handleValuePass1(Integer val) {
        if (prevVal != null && prevVal.equals(val)) {
            currentCount++;
        } else {
            currentCount = 1;
        }
        maxFreq = Math.max(maxFreq, currentCount);
        prevVal = val;
    }

    private void inorderPass1(TreeNode node) {
        if (node == null) return;
        inorderPass1(node.left);
        handleValuePass1(node.val);
        inorderPass1(node.right);
    }

    private void handleValuePass2(Integer val) {
        if (prevVal != null && prevVal.equals(val)) {
            currentCount++;
        } else {
            currentCount = 1;
        }
        if (currentCount == maxFreq) {
            // Add only the first element of a mode sequence
            if (modes.isEmpty() || !modes.get(modes.size() - 1).equals(val)) {
                modes.add(val);
            }
        }
        prevVal = val;
    }

    private void inorderPass2(TreeNode node) {
        if (node == null) return;
        inorderPass2(node.left);
        handleValuePass2(node.val);
        inorderPass2(node.right);
    }
}
```
### Algorithm
*   **Pass 1: Find Maximum Frequency**
    *   Initialize `maxFreq = 0`, `currentCount = 0`, and `prevVal` to a value outside the range of node values.
    *   Perform an in-order traversal. For each node, if its value is the same as the previous one, increment `currentCount`. Otherwise, reset `currentCount` to 1. Update `maxFreq` with the maximum `currentCount` seen so far.
    *   After the traversal, do a final update for `maxFreq` to account for the last sequence of numbers.
*   **Pass 2: Collect Modes**
    *   Initialize an empty list `modes`.
    *   Reset `currentCount` and `prevVal`.
    *   Perform a second in-order traversal.
    *   Count the occurrences of the current value sequence, same as in Pass 1.
    *   When a sequence of identical values ends, check if its count is equal to `maxFreq`. If it is, add the value to the `modes` list.
    *   After the traversal, perform a final check for the last sequence of values.
*   Convert the `modes` list to an array and return.

## Optimal One-Pass In-order Traversal
This is the most efficient approach. It builds upon the idea that an in-order traversal of a BST processes elements in sorted order. By traversing the tree just once, we can keep track of the current value's frequency, the maximum frequency seen so far, and the list of modes. When we find a new value with a frequency greater than the current maximum, we clear the modes list and start a new one. If we find a value with a frequency equal to the maximum, we add it to the list.
**Time:** O(N), as we traverse each node in the tree exactly once. · **Space:** O(H) for the recursion stack, where H is the height of the tree (worst case O(N), average case O(log N)). The space for the `modes` list is for the output and is not counted as extra space. This approach is considered O(1) auxiliary space.
**Pros:** Most efficient in terms of time, requiring only a single pass.; Space efficient, meeting the follow-up constraint.; Elegant solution that fully utilizes the BST's in-order traversal property.
**Cons:** Relies on class-level variables (or passing state through recursion), which can sometimes be less clean than a self-contained function.; The logic is slightly more complex than the HashMap approach.
### Explanation
We can optimize the two-pass approach into a single pass. The key insight is that during a single in-order traversal, we can update our list of modes dynamically. We maintain the frequency of the current element (`currentCount`) and the maximum frequency found so far (`maxFreq`).

As we traverse:
- If the current element's frequency (`currentCount`) becomes greater than `maxFreq`, it means we have found a new unique mode. We update `maxFreq`, clear our previous list of modes, and add the current element as the new mode.
- If `currentCount` equals `maxFreq`, it means we have found another element that is also a mode. We simply add it to our list of modes.
- If `currentCount` is less than `maxFreq`, we do nothing.

This allows us to determine the modes in a single pass, making it the most optimal solution.

```java
class Solution {
    private List<Integer> modes = new ArrayList<>();
    private int maxFreq = 0;
    private Integer prevVal = null;
    private int currentCount = 0;

    public int[] findMode(TreeNode root) {
        inorder(root);
        
        int[] result = new int[modes.size()];
        for (int i = 0; i < modes.size(); i++) {
            result[i] = modes.get(i);
        }
        return result;
    }

    private void inorder(TreeNode node) {
        if (node == null) {
            return;
        }

        // Traverse left subtree
        inorder(node.left);

        // Process current node
        if (prevVal != null && prevVal == node.val) {
            currentCount++;
        } else {
            currentCount = 1;
        }

        // Update modes list
        if (currentCount > maxFreq) {
            maxFreq = currentCount;
            modes.clear();
            modes.add(node.val);
        } else if (currentCount == maxFreq) {
            modes.add(node.val);
        }
        
        prevVal = node.val;

        // Traverse right subtree
        inorder(node.right);
    }
}
```
### Algorithm
*   Initialize class-level variables: `List<Integer> modes`, `int maxFreq = 0`, `Integer prevVal = null`, `int currentCount = 0`.
*   Create a recursive `inorder` helper function that takes a `TreeNode`.
*   The main `findMode` function will initialize the `modes` list, call `inorder(root)`, and then convert the `modes` list to an `int[]`.
*   **`inorder(node)` logic:**
    *   If `node` is null, return.
    *   Recursively call `inorder(node.left)`.
    *   **Process the current node:**
        *   If `prevVal` is not null and `node.val` is the same as `prevVal`, increment `currentCount`.
        *   Otherwise (it's the first node or a new value), reset `currentCount` to 1.
    *   **Update modes based on `currentCount`:**
        *   If `currentCount > maxFreq`: We've found a new, more frequent mode. Update `maxFreq = currentCount`, clear the `modes` list, and add `node.val` to it.
        *   Else if `currentCount == maxFreq`: We've found another value with the same top frequency. Add `node.val` to the `modes` list.
    *   Update `prevVal = node.val` to prepare for the next node.
    *   Recursively call `inorder(node.right)`.

# Solutions
### CSharp

```csharp
public class Solution {
    private int mx;
    private int cnt;
    private TreeNode prev;
    private List < int > res;
    public int[] FindMode(TreeNode root) {
        res = new List < int > ();
        Dfs(root);
        int[] ans = new int[res.Count];
        for (int i = 0; i < res.Count; ++i) {
            ans[i] = res[i];
        }
        return ans;
    }
    private void Dfs(TreeNode root) {
        if (root == null) {
            return;
        }
        Dfs(root.left);
        cnt = prev != null && prev.val == root.val ? cnt + 1 : 1;
        if (cnt > mx) {
            res = new List < int > (new int[] {
                root.val
            });
            mx = cnt;
        } else if (cnt == mx) {
            res.Add(root.val);
        }
        prev = root;
        Dfs(root.right);
    }
}
```

### Java

```java
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { private int mx ; private int cnt ; private TreeNode prev ; private List < Integer > res ; public int [] findMode ( TreeNode root ) { res = new ArrayList <>(); dfs ( root ); int [] ans = new int [ res . size ()]; for ( int i = 0 ; i < res . size (); ++ i ) { ans [ i ] = res . get ( i ); } return ans ; } private void dfs ( TreeNode root ) { if ( root == null ) { return ; } dfs ( root . left ); cnt = prev != null && prev . val == root . val ? cnt + 1 : 1 ; if ( cnt > mx ) { res = new ArrayList <>( Arrays . asList ( root . val )); mx = cnt ; } else if ( cnt == mx ) { res . add ( root . val ); } prev = root ; dfs ( root . right ); } }
```

### CPP

```cpp
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: TreeNode * prev ; int mx , cnt ; vector < int > ans ; vector < int > findMode ( TreeNode * root ) { dfs ( root ); return ans ; } void dfs ( TreeNode * root ) { if ( ! root ) return ; dfs ( root -> left ); cnt = prev != nullptr && prev -> val == root -> val ? cnt + 1 : 1 ; if ( cnt > mx ) { ans . clear (); ans . push_back ( root -> val ); mx = cnt ; } else if ( cnt == mx ) ans . push_back ( root -> val ); prev = root ; dfs ( root -> right ); } };
```

### Python

```python
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution : def findMode ( self , root : TreeNode ) -> List [ int ]: def dfs ( root ): if root is None : return nonlocal mx , prev , ans , cnt dfs ( root . left ) cnt = cnt + 1 if prev == root . val else 1 if cnt > mx : ans = [ root . val ] mx = cnt elif cnt == mx : ans . append ( root . val ) prev = root . val dfs ( root . right ) prev = None mx = cnt = 0 ans = [] dfs ( root ) return ans
```