Find Mode in Binary Search Tree - Solution & Explanation
Problem Statement
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
Follow up: Could you do that without using any extra space? (Assume that the implicit stack space incurred due to recursion does not count).
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.
This code performs two passes of inorder traversal. First, it determines the highest frequency of any value, then it constructs an array of all values with this frequency.
Complexity
Time Complexity: O(n), as each node is visited twice. Space Complexity: O(n) due to the recursion stack and the use of an array to store the modes.
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).
C implementation of Morris Traversal is complex and often requires intricate manipulation of node pointers. This outline conceptually placeholders the possible linking structure one would apply.
Complexity
Time Complexity: O(n), Space Complexity: O(1).
Approach 3: Default Approach
Try this approach in the editor →Complexity Comparison
| Approach | Complexity |
|---|---|
| Inorder Traversal with HashMap | Time Complexity: O(n), as each node is visited twice. Space Complexity: O(n) due to the recursion stack and the use of an array to store the modes. |
| Inorder Morris Traversal | Time Complexity: O(n), Space Complexity: O(1). |
| Default Approach | — |
Detailed 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. |
Video Solution
LeetCode 501. Find Mode in Binary Search Tree (Algorithm Explained) • Nick White • 23,757 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Find Mode in Binary Search Tree easy or hard?
Find Mode in Binary Search Tree Python/Java solution
How to solve Find Mode in Binary Search Tree in O(n)?
What is the best approach for Find Mode in Binary Search Tree?
Is Find Mode in Binary Search Tree asked at Google/Amazon/Meta?
What data structure is used in Find Mode in Binary Search Tree?
What is the time complexity of Find Mode in Binary Search Tree?
Ready to solve this problem?
Practice Find Mode in Binary Search Tree with our built-in code editor and test cases.
Practice on FleetCode