algoadvance

Given the root of a Binary Search Tree (BST), find the mode(s) (i.e., the most frequently occurred element) in the BST.

Constraints:

• The number of nodes in the tree is in the range [1, 10^4].
• -10^5 <= Node.val <= 10^5

Clarifying Questions

1. Q: Can there be multiple modes?
   • A: Yes, there can be multiple modes if multiple values occur with the same highest frequency.
2. Q: Can the tree contain duplicate values?
   • A: Yes, since the task involves finding the most frequent elements, duplicates are relevant.
3. Q: What should be the output format if there are multiple modes?
   • A: The output should be a list containing all the mode(s).
4. Q: Do we need to handle any special cases such as an empty tree?
   • A: No, it is guaranteed that there is at least one node in the tree.

Strategy

The strategy involves:

1. Performing an in-order traversal of the BST. This will help us retrieve values in a sorted manner (since it’s a BST).
2. Utilizing a dictionary (or collections.Counter) to count the frequency of each value.
3. Determine the maximum frequency from the collected frequencies.
4. Collect all the values that have this maximum frequency.

Code

from typing import Optional, List
from collections import Counter

# 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

def findMode(root: Optional[TreeNode]) -> List[int]:
    if not root:
        return []
    
    # Helper function to perform in-order traversal
    def inOrderTraversal(node, freq):
        if not node:
            return
        inOrderTraversal(node.left, freq)
        freq[node.val] += 1
        inOrderTraversal(node.right, freq)
    
    # Frequency dictionary
    freq = Counter()
    
    # Populate the frequency dictionary
    inOrderTraversal(root, freq)
    
    # Find the maximum frequency
    max_freq = max(freq.values())
    
    # Collect all the values that have the maximum frequency
    mode = [val for val, count in freq.items() if count == max_freq]
    
    return mode

Time Complexity

The time complexity of this approach is (O(n)), where (n) is the number of nodes in the BST.

• In-order Traversal: This takes (O(n)) time because we are visiting each node exactly once.
• Frequency Count Update: Each update operation in the Counter takes (O(1)) on average.
• Finding Max Frequency and Collecting Modes: Both these operations take (O(n)) time in the worst case because we might need to scan through all the items in the Counter.

Therefore, the overall time complexity is (O(n)).

Space Complexity

The space complexity is also (O(n)).

• The Counter will store up to (n) different values in the worst case.
• The space required for the recursion stack during the in-order traversal will be (O(h)) where (h) is the height of the tree. In the worst case (unbalanced tree), this could be (O(n)). In the best/average case (balanced tree), this would be (O(\log n)).

Thus, considering both the Counter and the recursion stack, the total space complexity is (O(n)).

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?