Watch 10 video solutions for Find Mode in Binary Search Tree, a easy level problem involving Tree, Depth-First Search, Binary Search Tree. This walkthrough by Nick White has 23,602 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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).
| 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. |