Given the root of a binary search tree (BST), find all the mode(s) in the BST. The mode is the value that appears most frequently. If there are multiple modes, return them in any order.
all of the modes (values with the highest frequency).values only.
Example:
Input: root = [1,null,2,2]
Output: [2]
To solve this problem, we need to determine which values in the BST appear most frequently. The brute-force idea is to traverse the tree and count how many times each value appears, then pick the value(s) with the highest count.
But, since it's a BST, we can use its properties to optimize. An in-order traversal of a BST gives values in sorted order. This means that duplicate values will appear consecutively. So, instead of using a hash map to count frequencies, we can simply count consecutive duplicates during an in-order traversal, keeping track of the max frequency and which value(s) have that frequency.
This approach uses less space and leverages the BST structure efficiently.
Here's how we can solve the problem step by step:
prev)count)max_count)max_count (modes)prev, increment count.count to 1.count == max_count, add the value to modes.count > max_count, update max_count and reset modes to just this value.modes list.
This approach only needs O(1) extra space (excluding the output and recursion stack).
Example Tree:
Input: [1, null, 2, 2]
The BST looks like:
1
\
2
/
2
prev = None, count = 0, max_count = 0, modes = []prev = None → count = 1 → max_count = 1 → modes = [1]prev = 1 → count = 1 (reset) → max_count = 1 → modes = [1, 2]prev = 2 → count = 2 → max_count = 2 → modes = [2] (reset to just 2)[2]Brute-force approach:
The optimized approach is faster in practice and uses less memory, especially for large trees with many duplicate values.
# 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):
self.prev = None
self.count = 0
self.max_count = 0
self.modes = []
def inorder(node):
if not node:
return
inorder(node.left)
if self.prev == node.val:
self.count += 1
else:
self.count = 1
if self.count == self.max_count:
self.modes.append(node.val)
elif self.count > self.max_count:
self.max_count = self.count
self.modes = [node.val]
self.prev = node.val
inorder(node.right)
inorder(root)
return self.modes
// Definition for a binary tree node.
// struct TreeNode {
// int val;
// TreeNode *left;
// TreeNode *right;
// TreeNode(int x) : val(x), left(NULL), right(NULL) {}
// };
class Solution {
public:
vector<int> modes;
int max_count = 0;
int count = 0;
int prev_val;
bool first = true;
void inorder(TreeNode* node) {
if (!node) return;
inorder(node->left);
if (first) {
count = 1;
first = false;
} else if (node->val == prev_val) {
count++;
} else {
count = 1;
}
if (count == max_count) {
modes.push_back(node->val);
} else if (count > max_count) {
max_count = count;
modes.clear();
modes.push_back(node->val);
}
prev_val = node->val;
inorder(node->right);
}
vector<int> findMode(TreeNode* root) {
inorder(root);
return modes;
}
};
// Definition for a binary tree node.
// public class TreeNode {
// int val;
// TreeNode left;
// TreeNode right;
// TreeNode(int x) { val = x; }
// }
import java.util.*;
public class Solution {
private Integer prev = null;
private int count = 0;
private int maxCount = 0;
private List<Integer> modes = new ArrayList<>();
public int[] findMode(TreeNode root) {
inorder(root);
int[] res = new int[modes.size()];
for (int i = 0; i < modes.size(); i++) {
res[i] = modes.get(i);
}
return res;
}
private void inorder(TreeNode node) {
if (node == null) return;
inorder(node.left);
if (prev != null && node.val == prev) {
count++;
} else {
count = 1;
}
if (count == maxCount) {
modes.add(node.val);
} else if (count > maxCount) {
maxCount = count;
modes.clear();
modes.add(node.val);
}
prev = node.val;
inorder(node.right);
}
}
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
var findMode = function(root) {
let prev = null;
let count = 0;
let maxCount = 0;
let modes = [];
function inorder(node) {
if (!node) return;
inorder(node.left);
if (prev !== null && node.val === prev) {
count++;
} else {
count = 1;
}
if (count === maxCount) {
modes.push(node.val);
} else if (count > maxCount) {
maxCount = count;
modes = [node.val];
}
prev = node.val;
inorder(node.right);
}
inorder(root);
return modes;
};
By leveraging the sorted order of BST in-order traversal, we can efficiently count consecutive duplicates and find the mode(s) in a single pass. This approach minimizes space usage and is both elegant and practical. The key insight is to track counts on-the-fly, rather than storing all frequencies in a hash map.