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 <= 105To solve #501 Find Mode in Binary Search Tree, the goal is to identify the value(s) that appear most frequently in the tree. Because the input structure is a Binary Search Tree (BST), an efficient approach leverages the fact that an in-order traversal processes nodes in sorted order. This means duplicate values appear consecutively, allowing us to count frequencies without extra storage.
During the traversal, maintain variables for the previous value, the current frequency, and the maximum frequency. As each node is visited, compare it with the previous value to update the count. If the current frequency exceeds the maximum frequency, update the result list. If it equals the maximum, append the value.
An alternative approach is performing a DFS traversal while storing frequencies in a hash map. This is simpler conceptually but uses extra space.
The optimized in-order method runs in O(n) time and can achieve O(1) additional space (excluding recursion stack) by exploiting BST properties.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| In-order Traversal (BST property) | O(n) | O(h) recursion stack |
| DFS with Hash Map | O(n) | O(n) |
Nick White
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.
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.
1var findMode = function(root) {
2 const freq = new Map();
3 inorder(root, freq);
4 let
JavaScript makes use of ES6 Maps and spreads to handle the frequency counting and maximum frequency determination.
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).
Time Complexity: O(n), Space Complexity: O(1).
1
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
In a binary search tree, in-order traversal visits nodes in sorted order. This means equal values appear next to each other, allowing you to count consecutive occurrences and determine the most frequent values efficiently.
Yes, variations of BST traversal and frequency counting problems are common in coding interviews. This problem tests understanding of tree traversal, BST properties, and how to optimize space usage during traversal.
The optimal approach uses an in-order traversal of the BST. Since in-order traversal produces sorted values, duplicates appear consecutively, making it easy to count frequencies and track the mode without using extra storage.
If you want a simple solution, a hash map can store the frequency of each value during a DFS traversal. However, the BST property allows an in-order traversal approach that avoids extra data structures and is more space efficient.
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.