Find Mode in Binary Search Tree - Video Solutions
LeetCode 501. Find Mode in Binary Search Tree (Algorithm Explained)
Find Mode in Binary Search Tree - Video Solution
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,757 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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).
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. |