#501

Easy

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

Find Mode in Binary Search Tree

Find Mode in Binary Search Tree asks to identify the most frequent element(s) in a BST using binary-tree traversal.

tree depth first search binary search tree binary tree

Problem Statement

Given the root of a binary search tree (BST) with duplicate values, you are tasked with finding all the mode(s) in the tree. A mode is defined as the most frequently occurring element in the tree. If there are multiple modes, return all of them in any order.

Assume a BST is defined such that for every node, its left children are smaller, and its right children are larger. The tree will be non-empty with nodes having values in the range [-10^5, 10^5]. The solution should efficiently traverse the tree and calculate the mode(s).

Examples

Example 1

Input: root = [1,null,2,2]

Output: [2]

Example details omitted.

Example 2

Input: root = [0]

Output: [0]

Example details omitted.

Constraints

The number of nodes in the tree is in the range [1, 104].
-105 <= Node.val <= 105

Solution Approach

In-order Traversal with State Tracking

The most efficient way to solve this is by performing an in-order traversal of the tree while keeping track of the frequency of each node's value. By utilizing a hashmap, you can efficiently count the occurrences of each value during the traversal.

Identify the Maximum Frequency

Once the traversal is complete, you can then identify the maximum frequency from the collected counts and determine the mode(s). This step is crucial for finding the correct output from the tracked frequencies.

Efficient Space Utilization

Although you need a hashmap to track frequencies, the problem can be solved with constant extra space for the result array (O(1) space complexity for the final output). This ensures the solution remains efficient even for large inputs.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(1)

The time complexity of the solution is O(n) because each node in the tree is visited exactly once during the in-order traversal. The space complexity is O(n) for storing the frequency map, but the result array is stored in constant space (O(1)) as it only holds the mode values.

What Interviewers Usually Probe

Can the candidate demonstrate efficient tree traversal and state tracking simultaneously?
Does the candidate understand how to manage space complexity while maintaining correctness?
How well does the candidate optimize the solution for large input sizes?

Common Pitfalls or Variants

Common pitfalls

Not considering the constant space complexity requirement for the final result array.
Forgetting to handle cases with multiple modes or ensuring that all modes are returned in the correct format.
Not accounting for the tree's potentially large size and failing to optimize the space and time complexity accordingly.

Follow-up variants

What if the tree is unbalanced? Does the solution still work efficiently?
How would the solution change if the problem required identifying the k most frequent elements instead of all modes?
Can the solution be modified to return the mode with the lowest value if there are multiple modes?

FAQ

What is the best traversal approach for finding the mode in a BST?

The best approach is to use an in-order traversal while keeping track of the frequency of each node's value in a hashmap.

How does in-order traversal work for solving the Find Mode in Binary Search Tree?

In-order traversal visits nodes in ascending order, which is ideal for a BST. As we traverse, we count each value's frequency and then identify the most frequent values.

What are the time and space complexities for this problem?

The time complexity is O(n) for the traversal, and the space complexity is O(n) due to the hashmap used for frequency tracking.

Can the solution handle a tree with only one node?

Yes, the solution works even if the tree has only one node, returning that single node as the mode.

What should I do if there are multiple modes in the tree?

If there are multiple modes, the solution will return all of them in any order. The key is to identify the maximum frequency and collect all values with that frequency.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

# Definition for a binary tree node.
# 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: TreeNode) -> List[int]:
        def dfs(root):
            if root is None:
                return
            nonlocal mx, prev, ans, cnt
            dfs(root.left)
            cnt = cnt + 1 if prev == root.val else 1
            if cnt > mx:
                ans = [root.val]
                mx = cnt
            elif cnt == mx:
                ans.append(root.val)
            prev = root.val
            dfs(root.right)

        prev = None
        mx = cnt = 0
        ans = []
        dfs(root)
        return ans

Continue Practicing

#530 minimum absolute difference in bst #538 convert bst to greater tree #449 serialize and deserialize bst