Difficulty: Easy | Acceptance: 58.90% | Paid: No Topics: Tree, Depth-First Search, Binary Search Tree, Binary Tree
Given the root of a binary search tree (BST) with duplicates, return all the mode(s) (i.e., the most frequently occurring 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.
- Examples
- Constraints
- Hash Map Frequency Count
- In-Order Traversal (BST Property)
- Morris Traversal
Examples
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, 10^4].
- -10^5 <= Node.val <= 10^5
Hash Map Frequency Count
Intuition Traverse the entire tree and count the frequency of every value using a hash map, then find the value(s) with the maximum frequency.
Steps
- Initialize a hash map to store value counts.
- Perform a traversal (DFS or BFS) of the tree.
- For each node visited, increment its count in the map.
- Iterate through the map to find the maximum frequency.
- Collect all values that match this maximum frequency into a result list.
python
from typing import List, Optional
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def findMode(self, root: Optional[TreeNode]) -> List[int]:
if not root:
return []
count_map = {}
def dfs(node):
if not node:
return
count_map[node.val] = count_map.get(node.val, 0) + 1
dfs(node.left)
dfs(node.right)
dfs(root)
max_freq = max(count_map.values())
return [k for k, v in count_map.items() if v == max_freq]
Complexity
- Time: O(N)
- Space: O(N)
- Notes: Uses extra space proportional to the number of unique values.
In-Order Traversal (BST Property)
Intuition An in-order traversal of a BST yields a sorted sequence of values. This means duplicate values will be adjacent. We can traverse the tree and count consecutive runs of identical values to find the mode without a hash map.
Steps
- Initialize variables to track the current value, current count, maximum count found so far, and the result list.
- Perform a recursive in-order traversal.
- If the current node’s value equals the previous value, increment the current count. Otherwise, reset the current count to 1.
- If the current count exceeds the maximum count, update the maximum count and reset the result list with the current value.
- If the current count equals the maximum count, append the current value to the result list.
python
from typing import List, Optional
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def findMode(self, root: Optional[TreeNode]) -> List[int]:
self.result = []
self.current_count = 0
self.max_count = 0
self.prev_val = None
def inorder(node):
if not node:
return
inorder(node.left)
if self.prev_val is None or node.val != self.prev_val:
self.current_count = 1
else:
self.current_count += 1
if self.current_count > self.max_count:
self.max_count = self.current_count
self.result = [node.val]
elif self.current_count == self.max_count:
self.result.append(node.val)
self.prev_val = node.val
inorder(node.right)
inorder(root)
return self.result
Complexity
- Time: O(N)
- Space: O(H) where H is the height of the tree (recursion stack).
- Notes: Optimizes space by utilizing the BST property, but still uses stack space for recursion.
Morris Traversal
Intuition We can achieve O(1) extra space (excluding the output) by using Morris Traversal. This allows us to perform an in-order traversal by temporarily modifying the tree structure (creating threads to predecessors) and then restoring it.
Steps
- Initialize current pointer to root.
- While current is not null:
- If current has no left child:
- Process current node (update counts and result list logic).
- Move to right child.
- Else:
- Find the inorder predecessor (rightmost node in left subtree).
- If predecessor’s right child is null:
- Link predecessor’s right to current (create thread).
- Move to left child.
- Else (predecessor’s right is current):
- Revert the link (predecessor’s right = null).
- Process current node.
- Move to right child.
- If current has no left child:
python
from typing import List, Optional
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def findMode(self, root: Optional[TreeNode]) -> List[int]:
if not root:
return []
result = []
current_count = 0
max_count = 0
prev_val = None
current = root
while current:
if not current.left:
# Process current
if prev_val is None or current.val != prev_val:
current_count = 1
else:
current_count += 1
if current_count > max_count:
max_count = current_count
result = [current.val]
elif current_count == max_count:
result.append(current.val)
prev_val = current.val
current = current.right
else:
# Find predecessor
predecessor = current.left
while predecessor.right and predecessor.right != current:
predecessor = predecessor.right
if not predecessor.right:
predecessor.right = current
current = current.left
else:
predecessor.right = None
# Process current
if prev_val is None or current.val != prev_val:
current_count = 1
else:
current_count += 1
if current_count > max_count:
max_count = current_count
result = [current.val]
elif current_count == max_count:
result.append(current.val)
prev_val = current.val
current = current.right
return result
Complexity
- Time: O(N)
- Space: O(1)
- Notes: Uses constant extra space by modifying the tree pointers temporarily, avoiding recursion stack overhead.