We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find Mode in Binary Search Tree

Number: 501

Difficulty: Easy

Paid? No

Companies: Amazon, Google, Bloomberg, Meta

Problem Description

Given the root of a binary search tree (BST) where duplicates are allowed, return all the mode(s) (i.e., the most frequently occurred element) found in the tree. In a BST, the left subtree of a node contains only nodes with keys less than or equal to the node's key, and the right subtree only contains keys greater than or equal to the node's key.

Key Insights

  • The BST in-order traversal yields a sorted order, which helps in counting consecutive duplicates.
  • A two-pass in-order traversal can be used: one pass to determine the maximum frequency (maxCount) and a second pass to collect all values that match this frequency.
  • The solution can be implemented without extra space (apart from recursion stack) by leveraging constant space counters and state variables.

Space and Time Complexity

Time Complexity: O(n), where n is the number of nodes, because each node is processed twice (once in each traversal). Space Complexity: O(h) where h is the height of the tree due to the recursion stack. O(1) extra space is used aside from this.

Solution

We perform an in-order traversal of the BST twice. The first traversal determines the maximum frequency of any value in the BST by comparing the current node's value with the previously visited node. Since the in-order traversal processes nodes in sorted order, duplicate values are consecutive, making the counting simple. After calculating maxCount, we reset our state and perform a second in-order traversal to collect all node values with frequency equal to maxCount. The key trick is to leverage the BST property (sorted in-order traversal) to count frequencies in one pass without using additional data structures like hash maps.

Code Solutions

# 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):
        # Initialize state variables: prev value, current frequency count, maximum frequency, and modes list.
        self.prev = None
        self.currentCount = 0
        self.maxCount = 0
        self.modes = []
        
        # First in-order traversal to find the maximum frequency (maxCount).
        def inorder_first(node):
            if not node:
                return
            inorder_first(node.left)
            # Update the count for the current node.
            if self.prev is None or node.val != self.prev:
                self.currentCount = 1
            else:
                self.currentCount += 1
            self.prev = node.val
            # Update maxCount if currentCount exceeds it.
            self.maxCount = max(self.maxCount, self.currentCount)
            inorder_first(node.right)
        
        inorder_first(root)
        
        # Second in-order traversal to collect all node values with frequency equal to maxCount.
        self.prev = None  # Reset previous value.
        self.currentCount = 0  # Reset count.
        
        def inorder_second(node):
            if not node:
                return
            inorder_second(node.left)
            if self.prev is None or node.val != self.prev:
                self.currentCount = 1
            else:
                self.currentCount += 1
            self.prev = node.val
            if self.currentCount == self.maxCount:
                self.modes.append(node.val)
            inorder_second(node.right)
        
        inorder_second(root)
        return self.modes
← Back to All Questions