{x}
blog image

Find Mode in Binary Search Tree

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:

  • 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.

 

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, 104].
  • -105 <= Node.val <= 105

 

Follow up: Could you do that without using any extra space? (Assume that the implicit stack space incurred due to recursion does not count).

Solution Explanation:

This problem asks to find the mode(s) (most frequent element(s)) in a Binary Search Tree (BST) that may contain duplicate values. The solution uses a depth-first search (DFS) approach with in-order traversal to efficiently find the mode. The key to optimization is leveraging the property of a BST, where elements are sorted during an inorder traversal.

Approach:

  1. In-order Traversal: We perform an in-order traversal of the BST. In-order traversal visits nodes in ascending order of their values. This is crucial because it allows us to easily count consecutive occurrences of the same value.

  2. Counting Consecutive Occurrences: We maintain three variables:

    • cnt: Counts the consecutive occurrences of the current node's value.
    • mx: Stores the maximum frequency encountered so far.
    • prev: Stores the previously visited node.

  3. Updating Mode:

    • If the current node's value is the same as the previous node's value (prev), we increment cnt.
    • Otherwise, it's a new value, so we reset cnt to 1.
    • If cnt exceeds mx, it means we've found a new mode with higher frequency, so we update mx and reset the result list ans with the current node's value.
    • If cnt equals mx, it means we've found another mode with the same highest frequency, so we append the current node's value to ans.

  4. Returning the Mode(s): After the traversal, ans contains all the modes of the BST.

Time and Space Complexity Analysis:

  • Time Complexity: O(N), where N is the number of nodes in the BST. This is because we perform a single in-order traversal of the tree, visiting each node exactly once.

  • Space Complexity: O(H) in the worst case, and O(log N) on average, where H is the height of the tree. This space is used for the recursive call stack during the DFS. In the worst-case scenario (a skewed tree), H can be equal to N, resulting in O(N) space complexity. However, in a balanced BST, the height is logarithmic with respect to the number of nodes, leading to O(log N) average space complexity. The space used for the ans list is at most O(N) in the worst case (all nodes have the same value).

Code Explanation (Python):

The Python code efficiently implements this approach. Note the use of nonlocal keyword to modify variables outside the scope of inner function dfs.

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

The other languages (Java, C++, Go, C#) follow a similar structure, adapting the syntax and data structures to their respective languages. The core algorithm remains the same, ensuring efficient in-order traversal and mode calculation.