LeetCode 501: Find Mode in Binary Search Tree Solution in Python – A Step-by-Step Guide

What Is LeetCode 501: Find Mode in Binary Search Tree?

In LeetCode 501: Find Mode in Binary Search Tree, you’re given the root of a BST, and your task is to find the mode—the value(s) that appear most frequently. A BST means every node’s left subtree has smaller values, and its right subtree has larger ones. If multiple values tie for the highest frequency, return them all. For example, in a tree with values [1, 2, 2], the mode is [2]. This problem tests your ability to traverse a tree and track frequencies, building on basics from LeetCode 94: Binary Tree Inorder Traversal.

Problem Statement

• Input: Root node of a BST (can be None).
• Output: List of integers—the mode(s) (most frequent values).
• Rules: If multiple modes exist, return them in any order; BST properties apply.

Constraints

• Number of nodes: 1 to 10⁴.
• Node values: -10⁵ to 10⁵.
• It’s a valid BST.

Examples

• Input: [1,null,2,2]
• Output: [2]
• Tree: 1 (root), 2 (right), 2 (right of 2). 2 appears twice, 1 once.
• Input: [0]
• Output: [0]
• Single node, mode is 0.
• Input: [1,1,2,null,null,2,2]
• Output: [1,2]
• Both 1 and 2 appear twice.

Understanding the Problem: Finding the Most Popular Values

To solve LeetCode 501 in Python, we need a function that traverses a BST and identifies the value(s) with the highest frequency. Since it’s a BST, an inorder traversal (left, root, right) gives values in sorted order, which we can use cleverly. We’ll explore:

• Best Solution (Inorder with O(1) Space): O(n) time, O(1) space—uses the sorted property to track counts without a hash map.
• Alternative Solution (Hash Map): O(n) time, O(n) space—counts frequencies explicitly.

Let’s dive into the O(1) space solution with a breakdown that’s easy to follow!

Best Solution: Inorder Traversal with O(1) Space

Why This Is the Best Solution

The inorder traversal with O(1) space is the star here because it’s memory-efficient. Since a BST’s inorder traversal yields sorted values, identical numbers appear consecutively. We can track the current value, its count, and the max count without storing everything—O(n) time, O(1) space (excluding recursion stack). It’s like counting votes as they come in, live, without a big tally sheet!

How It Works

Picture this as a walk through the tree:

• Step 1: Traverse Inorder:
• Visit left subtree, root, right subtree—values come in order.
• Step 2: Track Counts:
• Keep curr_val (current value), curr_count (its frequency), max_count (highest frequency seen), and modes (list of modes).
• Compare each value to the previous one.
• Step 3: Update Modes:
• If same as previous, increment curr_count.
• If new, check if curr_count beats or ties max_count, update modes, reset curr_count.
• Why It Works:
• BST ensures duplicates are adjacent in inorder.
• No extra space beyond a few variables.

It’s like a real-time mode tracker!

Step-by-Step Example

Example: [1,null,2,2]

• Tree:
``` 1 \ 2 / 2 ```
• Init: curr_val = None, curr_count = 0, max_count = 0, modes = [].
• Inorder: Left (none), 1, Right (2, 2).
• Node 1:
• curr_val = None, now 1.
• curr_count = 1.
• max_count = 0 < 1, update max_count = 1, modes = [1].
• Node 2 (left):
• curr_val = 1, now 2.
• Old count 1 = max_count, modes = [1].
• curr_count = 1, max_count = 1.
• Node 2 (right):
• curr_val = 2, same, curr_count = 2.
• curr_count = 2 > max_count = 1, max_count = 2, modes = [2].
• Result: [2].

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained for beginners:

Copy codeclass 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: TreeNode) -> List[int]:
        # Variables to track state
        self.curr_val = None    # Current value
        self.curr_count = 0     # Count of current value
        self.max_count = 0      # Highest frequency
        self.modes = []         # List of modes

        def inorder(node):
            if not node:
                return

            # Left subtree
            inorder(node.left)

            # Process current node
            if node.val == self.curr_val:
                self.curr_count += 1  # Same value, increment
            else:
                # New value, check previous
                if self.curr_count > self.max_count:
                    self.max_count = self.curr_count
                    self.modes = [self.curr_val]
                elif self.curr_count == self.max_count:
                    self.modes.append(self.curr_val)
                # Reset for new value
                self.curr_val = node.val
                self.curr_count = 1

            # Right subtree
            inorder(node.right)

        # Start traversal
        inorder(root)

        # Handle the last value
        if self.curr_count > self.max_count:
            self.max_count = self.curr_count
            self.modes = [self.curr_val]
        elif self.curr_count == self.max_count:
            self.modes.append(self.curr_val)

        return self.modes

• Lines 9-13: Class variables to track state across recursion.
• Lines 15-16: Base case—skip null nodes.
• Line 19: Recurse left (inorder).
• Lines 22-31: Process node:
• Same value: Increment curr_count.
• New value: Update modes if curr_count beats or ties max_count, reset counters.
• Line 34: Recurse right.
• Lines 38-43: Handle the final value after traversal ends.
• Time Complexity: O(n)—visit each node once.
• Space Complexity: O(1)—just a few variables (recursion stack is O(h), where h ≤ n).

It’s like a lean, mean mode-finding machine!

Alternative Solution: Using a Hash Map

Why an Alternative Approach?

The hash map solution is simpler to understand: count every value explicitly with a dictionary, then find the max frequency. It’s O(n) time and O(n) space—less efficient in space but very straightforward, especially if you’re new to BSTs.

How It Works

Think of this as a vote counter:

• Step 1: Traverse the tree (any order—preorder here).
• Step 2: Use a hash map to count each value’s frequency.
• Step 3: Find the max frequency and collect all values that match it.

It’s like tallying votes in a notebook!

Step-by-Step Example

Example: [1,null,2,2]

• Init: count = {}, max_count = 0, modes = [].
• Preorder: 1, 2, 2.
• count[1] = 1, max_count = 1.
• count[2] = 1, max_count = 1.
• count[2] = 2, max_count = 2.
• Find Modes:
• count[1] = 1 < 2, skip.
• count[2] = 2 = 2, add 2.
• Result: [2].

Code for Hash Map Approach

Copy codeclass Solution:
    def findMode(self, root: TreeNode) -> List[int]:
        if not root:
            return []

        # Count frequencies
        count = {}
        def preorder(node):
            if not node:
                return
            count[node.val] = count.get(node.val, 0) + 1
            preorder(node.left)
            preorder(node.right)

        preorder(root)

        # Find max frequency
        max_count = max(count.values())

        # Collect modes
        modes = [val for val, freq in count.items() if freq == max_count]

        return modes

• Time Complexity: O(n)—traverse and process n nodes.
• Space Complexity: O(n)—hash map stores all values.

It’s a simple vote counter!

Comparing the Two Solutions

• Inorder O(1) Space (Best):
• Pros: O(1) space, leverages BST property.
• Cons: Trickier logic.
• Hash Map (Alternative):
• Pros: Easy to follow, works for any tree.
• Cons: O(n) space.

Inorder wins for efficiency in a BST!

Additional Examples and Edge Cases

• [0]: [0]—single node.
• [1,1,1]: [1]—all same.
• [1,1,2,2]: [1,2]—tie.

Inorder handles them all gracefully.

Complexity Breakdown

• Inorder: Time O(n), Space O(1).
• Hash Map: Time O(n), Space O(n).

Inorder is the space-saver!

Key Takeaways

• BST Trick: Sorted inorder = consecutive duplicates.
• Space Matters: O(1) is possible—see Python Basics.
• Hash Maps: Simple but costly.
• Trees: Fun to traverse!

Final Thoughts: Find Those Modes!

LeetCode 501: Find Mode in Binary Search Tree in Python is a great mix of tree traversal and frequency counting. The inorder O(1) solution is a clever BST hack, while the hash map keeps it simple. Want more tree challenges? Try LeetCode 94: Binary Tree Inorder Traversal or LeetCode 235: Lowest Common Ancestor of a BST. Ready to explore? Head to Solve LeetCode 501 on LeetCode and find those modes today!