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:
Example 1:
Input: root = [1,null,2,2] Output: [2]
Example 2:
Input: root = [0] Output: [0]
Constraints:
[1, 104].-105 <= Node.val <= 105Follow up: Could you do that without using any extra space? (Assume that the implicit stack space incurred due to recursion does not count).
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).
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.
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.
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.
Time Complexity: O(n), Space Complexity: O(1).
| 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 | — |
| 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. |
LeetCode 501. Find Mode in Binary Search Tree (Algorithm Explained) • Nick White • 23,602 views views
Watch 9 more video solutions →Practice Find Mode in Binary Search Tree with our built-in code editor and test cases.
Practice on FleetCode