deepSWE.io

Find Mode in Binary Search Tree

Trees

Problem Statement

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.

Example

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

Output: [2]

Algorithm Explanation

A straightforward approach is to traverse the tree and use a hash map to store the frequency of each node's value. Then, we can find the maximum frequency and return all values with that frequency.

Algorithm Steps

In-order Traversal: We can perform an in-order traversal of the BST. This will give us the node values in sorted order.
Track Current Streak: As we traverse, we can keep track of the current value, its frequency (streak), and the maximum frequency seen so far.
Update Mode(s): If the current streak exceeds the maximum frequency, we clear our result list and add the current value. If the streak equals the maximum frequency, we just add the current value to the list.

Start

Starting in-order traversal.

Prev: null

Current Count: 0

Max Count: 0

Modes: []

Find Mode in BST Solution


class Solution:
    def findMode(self, root: Optional[TreeNode]) -> List[int]:
        self.prev = None
        self.max_count = 0
        self.current_count = 0
        self.modes = []

        self.inorder(root)
        
        return self.modes

    def inorder(self, node):
        if not node:
            return

        self.inorder(node.left)
        
        self.current_count = 1 if node.val != self.prev else self.current_count + 1
        
        if self.current_count == self.max_count:
            self.modes.append(node.val)
        elif self.current_count > self.max_count:
            self.max_count = self.current_count
            self.modes = [node.val]
            
        self.prev = node.val
        
        self.inorder(node.right)