Technical Interview Question

You are given a binary search tree. Write a function to find the mode(s) in the binary search tree, which is the value(s) that appear most frequently. Your function should return a list of mode(s) in ascending order.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def findMode(root: TreeNode) -> List[int]:
    # Your code here

Answer

To find the mode(s) in the binary search tree, we can use an in-order traversal to count the occurrence of each value. While traversing the tree, we track the current value and its count, and maintain the maximum count found so far. Once we have the maximum count, we perform another in-order traversal to collect all values with the maximum count.

Here's the implementation of the findMode function:

from typing import List

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def findMode(root: TreeNode) -> List[int]:
    def inOrderTraversal(node, value_count, max_count):
        if node is None:
            return

        inOrderTraversal(node.left, value_count, max_count)

        value_count[node.val] = value_count.get(node.val, 0) + 1
        max_count[0] = max(max_count[0], value_count[node.val])

        inOrderTraversal(node.right, value_count, max_count)

    def collectModes(node, value_count, max_count, result):
        if node is None:
            return

        collectModes(node.left, value_count, max_count, result)

        if value_count[node.val] == max_count[0]:
            result.append(node.val)

        collectModes(node.right, value_count, max_count, result)

    value_count = {}  # dictionary to store the count of each value
    max_count = [0]    # maximum count found so far
    inOrderTraversal(root, value_count, max_count)

    result = []
    collectModes(root, value_count, max_count, result)

    return result

This findMode function first initializes an empty dictionary value_count to store the count of each value, and a list max_count to store the maximum count found so far. It then recursively performs an in-order traversal on the binary search tree using the inOrderTraversal function to count the occurrences of each value and find the maximum count.

After that, it initializes an empty list result and uses the collectModes function to collect all values with the maximum count.

The time complexity of this solution is O(n) where n is the number of nodes in the binary search tree, as we are performing an in-order traversal of the entire tree twice and using a dictionary to store the count of each value.