Find Mode in Binary Search Tree — Problem & Solution
Find Mode in Binary Search Tree solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Find Mode in Binary Search Tree is an easy coding problem on depth-first search and trees, asked in Amazon, Google and Microsoft interviews.
- Difficulty: Easy
- Topics: Depth-First Search, Trees
- Asked at: Amazon, Google, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given the root of a binary search tree that may contain duplicate values. Return all of its modes — the values that occur most often — in ascending order.
Here a BST satisfies, at every node: every value in the left subtree is <= the node's value, and every value in the right subtree is >= it.
Example 1
Input: root = [1,null,2,2]
Output: [2]
Explanation: 2 occurs twice and 1 once.
Example 2
Input: root = [0]
Output: [0]
Example 3
Input: root = [5,3,7,3,5,6,7]
Output: [3,5,7]
Explanation: 3, 5 and 7 each occur twice; 6 once. All three are modes, listed ascending.
Constraints
The number of nodes in the tree is in the range [1, 10^4]-10^5 <= Node.val <= 10^5
Follow-up: Could you do it without a hash map — using no extra space apart from the recursion or traversal stack?
Hints for Find Mode in Binary Search Tree
Hint 1
An inorder walk of a BST visits its values in non-decreasing order, so equal values come out next to each other.
Hint 2
Count the length of each run of equal values as the walk produces them, remembering the longest run so far.
Hint 3
When a run beats the best count, restart the answer with that value; when it ties, append it. Values arrive ascending, so the answer is already sorted.
How to solve Find Mode in Binary Search Tree
Inorder traversal turns the BST into a sorted sequence, where every value's copies form one contiguous run. The modes are the values with the longest runs, found in one pass with a run counter and a best counter — no hash map.
Approach
- Walk the tree inorder (an explicit stack or recursion).
- For each value: if it equals the previous one, increment
count; otherwise resetcount = 1. - If
count > best, setbest = countand make the answer just[value]; ifcount == best, appendvalue. - After the walk, the answer holds every mode in ascending order.
Why it works
With left <= node <= right at every node, inorder emits the values in non-decreasing order, so all copies of a value are consecutive and count reaches that value's total frequency at its last copy. A value is kept in the answer exactly when that frequency equals the final maximum — any value kept earlier for a smaller best is discarded when the answer restarts.
Complexity
- Time —
O(n) - Space —
O(h) for the traversal stack, besides the output
Pitfalls
- Restart the list when
count > bestand append only whencount == best; a value appended on a tie and then extended simply restarts the list with itself, so it is never listed twice. - Several modes are possible; all of them must be returned.
- Do not assume distinct values: this BST allows duplicates on either side.
Reference solution
Python
from typing import List, Optional
def findMode(root: Optional[TreeNode]) -> List[int]:
modes = []
best = count = 0
prev = None
stack = []
cur = root
while cur is not None or stack:
while cur is not None:
stack.append(cur)
cur = cur.left
cur = stack.pop()
count = count + 1 if cur.val == prev else 1
prev = cur.val
if count > best:
best = count
modes = [cur.val]
elif count == best:
modes.append(cur.val)
cur = cur.right
return modesJava
public static int[] findMode(TreeNode root) {
List<Integer> modes = new ArrayList<>();
int best = 0, count = 0;
long prev = Long.MIN_VALUE;
Deque<TreeNode> stack = new ArrayDeque<>();
TreeNode cur = root;
while (cur != null || !stack.isEmpty()) {
while (cur != null) {
stack.push(cur);
cur = cur.left;
}
cur = stack.pop();
count = cur.val == prev ? count + 1 : 1;
prev = cur.val;
if (count > best) {
best = count;
modes.clear();
modes.add(cur.val);
} else if (count == best) {
modes.add(cur.val);
}
cur = cur.right;
}
int[] res = new int[modes.size()];
for (int i = 0; i < res.length; i++) res[i] = modes.get(i);
return res;
}C++
vector<int> findMode(TreeNode* root) {
vector<int> modes;
int best = 0, count = 0;
long long prev = LLONG_MIN;
vector<TreeNode*> stack;
TreeNode* cur = root;
while (cur || !stack.empty()) {
while (cur) {
stack.push_back(cur);
cur = cur->left;
}
cur = stack.back();
stack.pop_back();
count = cur->val == prev ? count + 1 : 1;
prev = cur->val;
if (count > best) {
best = count;
modes.assign(1, cur->val);
} else if (count == best) {
modes.push_back(cur->val);
}
cur = cur->right;
}
return modes;
}JavaScript
var findMode = function(root) {
var modes = [], best = 0, count = 0, prev = null;
var stack = [], cur = root;
while (cur !== null || stack.length > 0) {
while (cur !== null) {
stack.push(cur);
cur = cur.left;
}
cur = stack.pop();
count = cur.val === prev ? count + 1 : 1;
prev = cur.val;
if (count > best) {
best = count;
modes = [cur.val];
} else if (count === best) {
modes.push(cur.val);
}
cur = cur.right;
}
return modes;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 201 depth-first search problems · the whole catalogue
Learn the technique: Depth-First Search (DFS) · Binary Trees and Tree Traversals