Find Mode in Binary Search Tree solution and explanation
Google
9 more videos on this problem
LeetCode 501. Find Mode in Binary Search Tree (Algorithm Explained)Nick White · 10:53 · 23K views
Find Mode in Binary Search Tree | 2 Approaches | Follow Up | Leetcode-501 | GOOGLEcodestorywithMIK · 17:57 · 10K views
Find Mode in Binary Search Tree - LeetCode #501 - Inorder Traversal - PythonCodingNinja · 8:07 · 2K views
501. Find Mode in Binary Search Tree - Daily Leetcode (Day 12)yeetcode · 6:43 · 2K views
501. Find Mode in Binary Search Tree - Morris TraversalTechTalk · 9:16 · 1K views
Find Mode in Binary Search Tree | Leetcode 501 | Amazon Google Facebook interview questionSuper Lazy Coder · 15:45 · 1K views
LeetCode 501 Find Mode in Binary Search Tree - FAANG Interview Question.AlgorithmicIQ · 4:31 · 1K views
✅ Find Mode in Binary Search Tree ✅ Explained In Detail - Java - Leetcode - 501 - Easiest ApproachLeet Logics · 9:53 · 1K views
501. Find Mode in Binary Search Tree (Leetcode Easy)Programming Live with Larry · 22:42 · 1K views
Solving LeetCode 501: Find Mode in Binary Search Tree | In-order traversalCode Harmony · 11:18 · 805 views
The problem
Given the root of a binary search tree (BST) with duplicates, return all the mode(s) (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:
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
Approach overview
Problem Overview: Given the root of a Binary Search Tree (BST), return all values that appear most frequently. The result may contain multiple modes if several values share the same highest frequency.
The key observation is that an binary search tree produces a sorted sequence when traversed using inorder traversal. Equal values appear consecutively, which allows frequency counting without needing to sort or reorder nodes.
Approach 1: Inorder Traversal with HashMap (O(n) time, O(n) space)
Traverse the tree using inorder depth-first search and record the frequency of each value in a hash map. Every time you visit a node, increment map[node.val]. After traversal, scan the map to determine the maximum frequency and collect all keys that match it.
This method works for any binary tree, not just BSTs. The logic is simple: one traversal to count, another pass over the map to extract modes. Hash lookups and increments run in constant time, giving overall O(n) time complexity with O(n) extra space for the map. This approach is straightforward and easy to implement during interviews when memory constraints are not strict.
Approach 2: Inorder Morris Traversal (O(n) time, O(1) space)
A BST guarantees sorted order during inorder traversal, so equal values appear in consecutive positions. Instead of storing counts for every value, track only three variables: currentCount, maxCount, and previousValue. When visiting nodes in sorted order, increment the count if the value matches the previous one; otherwise reset it to 1. Update the result list whenever the count equals or exceeds the maximum frequency.
Morris traversal allows inorder traversal without recursion or a stack by temporarily modifying tree pointers. Each node is visited twice at most, so the algorithm still runs in O(n) time while using O(1) auxiliary space. This is the most memory‑efficient solution and leverages the BST property directly.
Recommended for interviews: Start with the HashMap counting approach to demonstrate the basic idea of frequency tracking. Then optimize using inorder traversal properties of a BST. The Morris traversal version is usually considered the optimal solution because it keeps the O(n) time complexity while reducing auxiliary space to O(1).
Approach 1: Inorder Traversal with HashMap
This approach uses an inorder traversal to exploit the nature of BSTs, where an inorder traversal yields elements in sorted order. Utilize a HashMap (or equivalent) to count the frequency of each element. Traverse the tree, update frequencies, and then determine the mode(s) based on maximum frequency.
class Solution:
def findMode(self, root: TreeNode) -> List[int]:
from collections import defaultdict
freq = defaultdict(int)
self.inorder(root, freq)
max_freq = max(freq.values())
return [key for key, value in freq.items() if value == max_freq]
def inorder(self, root, freq):
if not root:
return
self.inorder(root.left, freq)
freq[root.val] += 1
self.inorder(root.right, freq)import java.util.*;
public class Solution {
public int[] findMode(TreeNode root) {
Map<Integer, Integer> freqMap = new HashMap<>();
inorder(root, freqMap);
return findMaxFreq(freqMap);
}
private void inorder(TreeNode root, Map<Integer, Integer> freqMap) {
if (root == null) return;
inorder(root.left, freqMap);
freqMap.put(root.val, freqMap.getOrDefault(root.val, 0) + 1);
inorder(root.right, freqMap);
}
private int[] findMaxFreq(Map<Integer, Integer> freqMap) {
int maxFreq = 0;
for (int freq : freqMap.values()) {
maxFreq = Math.max(maxFreq, freq);
}
List<Integer> modes = new ArrayList<>();
for (int key : freqMap.keySet()) {
if (freqMap.get(key) == maxFreq) {
modes.add(key);
}
}
return modes.stream().mapToInt(i -> i).toArray();
}
}#include <vector>
#include <unordered_map>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
vector<int> findMode(TreeNode* root) {
unordered_map<int, int> freq;
inorder(root, freq);
return findMaxFreq(freq);
}
void inorder(TreeNode* root, unordered_map<int, int>& freq) {
if (!root) return;
inorder(root->left, freq);
freq[root->val]++;
inorder(root->right, freq);
}
vector<int> findMaxFreq(unordered_map<int, int>& freq) {
int maxFreq = 0;
for (const auto& p : freq) {
maxFreq = max(maxFreq, p.second);
}
vector<int> modes;
for (const auto& p : freq) {
if (p.second == maxFreq) {
modes.push_back(p.first);
}
}
return modes;
}
};var findMode = function(root) {
const freq = new Map();
inorder(root, freq);
let maxFreq = Math.max(...freq.values());
const modes = [];
for (const [key, value] of freq) {
if (value === maxFreq) {
modes.push(key);
}
}
return modes;
};
function inorder(root, freq) {
if (!root) return;
inorder(root.left, freq);
freq.set(root.val, (freq.get(root.val) || 0) + 1);
inorder(root.right, freq);
}#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
// Helper function to do inorder traversal and record frequency
void inorder(struct TreeNode* root, int *modeCount, int *maxCount, int lastVal, int currentCount) {
if (root == NULL) return;
inorder(root->left, modeCount, maxCount, lastVal, currentCount);
if (lastVal == root->val) {
currentCount++;
} else {
currentCount = 1;
}
if (currentCount > *maxCount) {
*maxCount = currentCount;
*modeCount = 1;
} else if (currentCount == *maxCount) {
(*modeCount)++;
}
lastVal = root->val;
inorder(root->right, modeCount, maxCount, lastVal, currentCount);
}
// Fill modes array
void findModes(struct TreeNode* root, int *modes, int *index, int maxCount, int lastVal, int currentCount) {
if (root == NULL) return;
findModes(root->left, modes, index, maxCount, lastVal, currentCount);
if (lastVal == root->val) {
currentCount++;
} else {
currentCount = 1;
}
if (currentCount == maxCount) {
modes[*index] = root->val;
(*index)++;
}
lastVal = root->val;
findModes(root->right, modes, index, maxCount, lastVal, currentCount);
}
int* findMode(struct TreeNode* root, int* returnSize) {
int modeCount = 0, maxCount = 0;
inorder(root, &modeCount, &maxCount, INT_MIN, 0);
int* modes = (int*)malloc(sizeof(int) * modeCount);
int index = 0;
findModes(root, modes, &index, maxCount, INT_MIN, 0);
*returnSize = modeCount;
return modes;
}using System;
using System.Collections.Generic;
public class Solution {
public int[] FindMode(TreeNode root) {
var freq = new Dictionary<int, int>();
Inorder(root, freq);
int maxFreq = GetMaxFreq(freq);
var modes = new List<int>();
foreach (var kvp in freq) {
if (kvp.Value == maxFreq) {
modes.Add(kvp.Key);
}
}
return modes.ToArray();
}
private void Inorder(TreeNode root, Dictionary<int, int> freq) {
if (root == null) return;
Inorder(root.left, freq);
if (freq.ContainsKey(root.val)) {
freq[root.val]++;
} else {
freq[root.val] = 1;
}
Inorder(root.right, freq);
}
private int GetMaxFreq(Dictionary<int, int> freq) {
int maxFreq = 0;
foreach (var count in freq.Values) {
if (count > maxFreq) {
maxFreq = count;
}
}
return maxFreq;
}
}The Python solution takes advantage of default dictionaries to simplify frequency tracking, then list comprehension to identify modes.
Time Complexity: O(n), Space Complexity: O(n) due to the defaultdict storing frequencies.
Approach 2: Inorder Morris Traversal
Morris Traversal allows inorder traversal without using additional stack space, which could be advantageous in follow-up scenarios described by the problem constraints. By threading the tree, we can traverse without recursion or explicit stack, maintaining a space complexity of O(1).
class Solution:
def findMode(self, root: TreeNode) -> List[int]:
# Placeholder for Morris Traversal implementation.
return []public class Solution {
public int[] findMode(TreeNode root) {
// Placeholder code for Morris Traversal approach.
return new int[0];
}
}#include <vector>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
vector<int> findMode(TreeNode* root) {
// Placeholder for Morris Traversal approach.
return vector<int>();
}
};var findMode = function(root) {
// Placeholder for Morris Traversal implementation.
return [];
};#include <stdio.h>
#include <stdlib.h>
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
int* findMode(struct TreeNode* root, int* returnSize) {
// Placeholder code, as Morris Traversal for mode requires intricate linking.
*returnSize = 0;
return NULL;
}public class Solution {
public int[] FindMode(TreeNode root) {
// Placeholder code for Morris Traversal method.
return new int[0];
}
}This Python snippet illustrates potential space-saving compliance through Morris Traversal groundwork, focusing on conceptual insight over implementation.
Time Complexity: O(n), Space Complexity: O(1).
Approach 3: Default Approach
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func findMode(root *TreeNode) []int {
mx, cnt := 0, 0
var prev *TreeNode
var ans []int
var dfs func(root *TreeNode)
dfs = func(root *TreeNode) {
if root == nil {
return
}
dfs(root.Left)
if prev != nil && prev.Val == root.Val {
cnt++
} else {
cnt = 1
}
if cnt > mx {
ans = []int{root.Val}
mx = cnt
} else if cnt == mx {
ans = append(ans, root.Val)
}
prev = root
dfs(root.Right)
}
dfs(root)
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| Inorder Traversal with HashMap | Time Complexity: O(n), Space Complexity: O(n) due to the defaultdict storing frequencies. |
| Inorder Morris Traversal | Time Complexity: O(n), Space Complexity: O(1). |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Inorder Traversal with HashMap | O(n) | O(n) | Simple implementation when extra memory is acceptable or when the tree is not guaranteed to be a BST. |
| Inorder Morris Traversal | O(n) | O(1) | Best for BSTs when minimizing auxiliary space and avoiding recursion or stacks. |
Frequently asked questions
Is Find Mode in Binary Search Tree easy or hard?
The problem is rated Easy on LeetCode with an acceptance rate around 58%. The HashMap approach is straightforward, while the optimized constant-space solution requires deeper understanding of BST inorder traversal and Morris traversal techniques.
Find Mode in Binary Search Tree Python/Java solution
Python and Java solutions typically perform an inorder traversal and count occurrences. The simple approach stores frequencies in a dictionary or HashMap, while the optimized version tracks counts of consecutive values during traversal and updates the result list dynamically.
How to solve Find Mode in Binary Search Tree in O(n)?
Perform an inorder traversal so values are visited in sorted order. Track the previous value and maintain a running frequency counter for consecutive duplicates. Update the maximum frequency and store values that match it. Each node is processed once, resulting in O(n) time complexity.
What is the best approach for Find Mode in Binary Search Tree?
The optimal approach uses inorder traversal of the BST while counting consecutive values. Because inorder traversal produces sorted values, duplicates appear next to each other, allowing frequency tracking with only a few variables. Using Morris traversal reduces auxiliary space to O(1) while maintaining O(n) time complexity.
Is Find Mode in Binary Search Tree asked at Google/Amazon/Meta?
Binary tree and BST traversal problems frequently appear in interviews at companies like Amazon, Google, and Meta. Variants involving inorder traversal, frequency counting, or BST properties are common in coding interview question sets.
What data structure is used in Find Mode in Binary Search Tree?
The most common implementation uses a hash map to count frequencies during traversal. Optimized solutions rely on the BST property and track counts during inorder traversal without extra data structures, sometimes using Morris traversal to achieve O(1) space.
What is the time complexity of Find Mode in Binary Search Tree?
All efficient solutions run in O(n) time because every node in the tree must be visited at least once. The HashMap counting approach uses O(n) space, while the Morris inorder traversal approach reduces auxiliary space to O(1).