Domain 1EasyCORE

Find Mode in Binary Search Tree

The problem asks us to find all the mode(s) in a binary search tree (BST). The modes are the values that appear most frequently in the tree. If there are multiple modes, we can return them in any order. The BST has duplicates, and we need to consider this when counting frequencies.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Tree

501. Find Mode in Binary Search Tree

Model: qwen2.5-coder:14b
Topics: Tree
FAANG asked: 1
Acceptance rate: 43.7%


Problem Breakdown

The problem asks us to find all the mode(s) in a binary search tree (BST). The modes are the values that appear most frequently in the tree. If there are multiple modes, we can return them in any order. The BST has duplicates, and we need to consider this when counting frequencies.

Inputs:

  • root: The root node of a binary search tree.

Outputs:

  • A list of integers representing the mode(s) of the BST.

Implicit Constraints or Tricky Edge Cases:

  • The tree can have duplicate values.
  • The tree can be empty (though the problem guarantees at least one node).
  • Negative numbers are possible in the tree.

Intuition

A brute-force approach would involve traversing the entire tree to count the frequency of each value and then determining which value(s) have the highest frequency. This approach would require O(n) time complexity for traversal and O(n) space complexity for storing frequencies, where n is the number of nodes in the tree.

However, we can leverage the properties of a BST to improve our solution. In-order traversal of a BST yields values in non-decreasing order. By keeping track of the current value’s frequency and comparing it with the maximum frequency found so far, we can efficiently determine the mode(s) without needing extra space for counting frequencies.

Approach

  1. In-order Traversal: Perform an in-order traversal of the BST to process nodes in non-decreasing order.
  2. Frequency Tracking: Use variables to track the current value’s frequency (current_count), the maximum frequency found so far (max_count), and a list to store the modes (modes).
  3. Update Logic:
    • If the current node’s value is different from the previous one, reset current_count to 1.
    • If current_count equals max_count, add the current value to modes.
    • If current_count exceeds max_count, update max_count and reset modes to contain only the current value.
  4. Edge Cases: Handle cases where the tree is empty or has only one node.

Complexity Analysis

  • Time Complexity: O(n), where n is the number of nodes in the tree. We visit each node exactly once during the in-order traversal.
  • Space Complexity: O(1) (excluding the space required for the output list). We use a constant amount of extra space for variables and do not store frequencies in additional data structures.

Solution

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]:
    if not root:
        return []
    
    modes = []
    current_count = 0
    max_count = 0
    prev_val = None
    
    def inorder_traversal(node):
        nonlocal current_count, max_count, prev_val, modes
        
        if node is None:
            return
        
        # Traverse the left subtree
        inorder_traversal(node.left)
        
        # Process the current node
        if prev_val is not None and prev_val == node.val:
            current_count += 1
        else:
            current_count = 1
        
        if current_count > max_count:
            max_count = current_count
            modes = [node.val]
        elif current_count == max_count:
            modes.append(node.val)
        
        prev_val = node.val
        
        # Traverse the right subtree
        inorder_traversal(node.right)
    
    inorder_traversal(root)
    return modes

Edge Cases Handled

  • Empty Tree: The function returns an empty list if the input tree is empty.
  • Single Node Tree: If the tree has only one node, that node’s value is returned as the mode.
  • All Nodes Have Same Value: All nodes having the same value will be correctly identified as modes.
  • Multiple Modes: If there are multiple values with the same highest frequency, all such values are included in the result.