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).
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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
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). |
LeetCode 501. Find Mode in Binary Search Tree (Algorithm Explained) • Nick White • 22,704 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