LeetCode 501 - Find Mode in Binary Search Tree

LeetCode Problem 501

Difficulty: 🟢 Easy
Topics: Tree, Depth-First Search, Binary Search Tree, Binary Tree

Solution

Problem Understanding

This problem asks us to find the mode(s) in a Binary Search Tree (BST). A mode is the value that appears most frequently in the tree. Since duplicates are allowed in this BST definition, a value may occur multiple times.

The input is the root node of a BST. Every node contains an integer value and pointers to left and right children. Because the tree is a BST, values in the left subtree are less than or equal to the current node’s value, and values in the right subtree are greater than or equal to the current node’s value.

The expected output is a list of integers representing all values that appear with the highest frequency. If multiple values are tied for the maximum count, we return all of them in any order.

The constraints tell us that the tree contains between 1 and 10^4 nodes. Since the tree size is relatively moderate, an O(n) traversal is completely feasible. However, solutions worse than linear time would become unnecessarily inefficient.

The BST property is particularly important here. Since an inorder traversal of a BST produces values in sorted order, duplicates will appear consecutively. This means we can count repeated values without using a hash map.

There are several edge cases worth considering:

• A tree with only one node, where that value must be the mode.
• A tree where every value is unique, meaning every value appears once and all values are modes.
• A tree where multiple values tie for highest frequency.
• A tree where all nodes contain the same value.
• Deeply skewed trees that resemble linked lists.

The problem also includes a follow-up asking whether we can solve it without extra space, excluding recursion stack space. This strongly hints that we should exploit the BST ordering instead of using a frequency map.

Approaches

Brute Force Approach

A straightforward solution is to traverse the tree and count the frequency of every value using a hash map.

We can perform a DFS traversal and maintain a dictionary where keys are node values and values are occurrence counts. After traversal, we scan the dictionary to find the maximum frequency and collect all keys with that count.

This works because every node is visited exactly once, and the frequency map accurately records occurrences.

However, this approach uses additional memory proportional to the number of unique values in the tree. Since the BST property gives us sorted ordering during inorder traversal, we can do better and avoid storing all frequencies.

Optimal Approach

The key observation is that inorder traversal of a BST visits nodes in sorted order.

Because duplicate values appear consecutively, we only need to track:

• The previously visited value
• The current streak count
• The highest frequency seen so far
• The list of modes

As we traverse:

• If the current value matches the previous one, increment the count.
• Otherwise, reset the count to 1.
• If the count exceeds the maximum frequency, update the modes list.
• If the count equals the maximum frequency, append the value.

This avoids a hash map entirely and only requires tracking a few variables.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(n)	DFS traversal with hash map frequency counting
Optimal	O(n)	O(h)	Inorder traversal using BST ordering, where h is tree height

The optimal solution uses only recursion stack space. In a balanced BST this is O(log n), while in the worst case of a skewed tree it becomes O(n).

Algorithm Walkthrough

1. Initialize tracking variables.

We keep:

• previous_value to remember the last node value seen.
• current_count to count consecutive occurrences.
• max_frequency to track the highest count encountered.
• modes to store the most frequent values.

2. Perform an inorder traversal.

We recursively traverse the left subtree, process the current node, then traverse the right subtree.

This ordering is important because inorder traversal of a BST produces values in sorted order. 3. Update the running frequency.

When visiting a node:

• If its value matches previous_value, increment current_count.
• Otherwise, reset current_count to 1.

Then update previous_value to the current node value. 4. Compare against the maximum frequency.

If current_count > max_frequency, we found a new mode:

• Update max_frequency
• Reset modes to contain only this value

If current_count == max_frequency, this value ties with the current mode frequency, so append it. 5. Continue traversal until all nodes are processed.

After traversal finishes, return modes.

Why it works

The correctness relies on the BST inorder property. Since values appear in sorted order, duplicate values are grouped together. This guarantees that maintaining a running count of consecutive equal values correctly measures each value’s frequency. By updating the mode list whenever a higher or equal frequency is found, the algorithm ensures that every most frequent value is included in the final result.

Python Solution

# 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

from typing import List, Optional

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

        def inorder(node: Optional[TreeNode]) -> None:
            nonlocal previous_value, current_count, max_frequency

            if not node:
                return

            inorder(node.left)

            if previous_value == node.val:
                current_count += 1
            else:
                current_count = 1

            previous_value = node.val

            if current_count > max_frequency:
                max_frequency = current_count
                modes.clear()
                modes.append(node.val)
            elif current_count == max_frequency:
                modes.append(node.val)

            inorder(node.right)

        inorder(root)
        return modes

The implementation uses a nested inorder function to recursively traverse the BST. The recursion naturally follows the inorder sequence, which guarantees sorted values.

The previous_value variable keeps track of the most recently processed node. If the current node has the same value, we increment the running frequency. Otherwise, we reset it to 1 because we have encountered a new value.

Whenever the running count exceeds the maximum frequency, we clear the modes list and insert the current value as the new sole mode. If the frequency matches the maximum, we append the value since it ties with existing modes.

Finally, after traversal finishes, the accumulated modes list is returned.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func findMode(root *TreeNode) []int {
	var modes []int
	var previous *int
	currentCount := 0
	maxFrequency := 0

	var inorder func(node *TreeNode)

	inorder = func(node *TreeNode) {
		if node == nil {
			return
		}

		inorder(node.Left)

		if previous != nil && *previous == node.Val {
			currentCount++
		} else {
			currentCount = 1
		}

		value := node.Val
		previous = &value

		if currentCount > maxFrequency {
			maxFrequency = currentCount
			modes = []int{node.Val}
		} else if currentCount == maxFrequency {
			modes = append(modes, node.Val)
		}

		inorder(node.Right)
	}

	inorder(root)

	return modes
}

The Go implementation follows the exact same logic as the Python version. Since Go does not have None, we use a pointer *int for previous to distinguish between an uninitialized value and an actual integer.

Slices are used for the modes result. When a new maximum frequency is found, we replace the slice with a new slice containing only the current value.

No integer overflow concerns exist here because node counts are limited to 10^4.

Worked Examples

Example 1

Input:

root = [1,null,2,2]

Tree structure:

    1
     \
      2
     /
    2

Inorder traversal produces:

[1, 2, 2]

Step	Current Value	Previous Value	Current Count	Max Frequency	Modes
1	1	None	1	1	[1]
2	2	1	1	1	[1, 2]
3	2	2	2	2	[2]

Final result:

[2]

Example 2

Input:

root = [0]

Inorder traversal:

[0]

Step	Current Value	Previous Value	Current Count	Max Frequency	Modes
1	0	None	1	1	[0]

Final result:

[0]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Every node is visited exactly once
Space	O(h)	Recursion stack depth equals tree height

The algorithm performs a single inorder traversal, touching every node once, which gives linear time complexity.

The auxiliary space comes only from recursion. In a balanced tree, height is O(log n). In the worst case of a completely skewed tree, height becomes O(n).

Test Cases

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

solution = Solution()

# Example 1: [1, null, 2, 2]
root1 = TreeNode(1)
root1.right = TreeNode(2)
root1.right.left = TreeNode(2)
assert solution.findMode(root1) == [2]  # duplicate mode

# Example 2: [0]
root2 = TreeNode(0)
assert solution.findMode(root2) == [0]  # single node

# All unique values
root3 = TreeNode(2)
root3.left = TreeNode(1)
root3.right = TreeNode(3)
assert sorted(solution.findMode(root3)) == [1, 2, 3]  # every value appears once

# All same values
root4 = TreeNode(2)
root4.left = TreeNode(2)
root4.right = TreeNode(2)
assert solution.findMode(root4) == [2]  # single repeated mode

# Multiple modes
root5 = TreeNode(2)
root5.left = TreeNode(1)
root5.right = TreeNode(3)
root5.left.left = TreeNode(1)
root5.right.right = TreeNode(3)
assert sorted(solution.findMode(root5)) == [1, 3]  # tied frequencies

# Left-skewed tree
root6 = TreeNode(3)
root6.left = TreeNode(2)
root6.left.left = TreeNode(2)
root6.left.left.left = TreeNode(1)
assert solution.findMode(root6) == [2]  # skewed tree structure

# Negative values
root7 = TreeNode(-1)
root7.left = TreeNode(-2)
root7.right = TreeNode(-1)
assert solution.findMode(root7) == [-1]  # negative numbers

# Large duplicate chain
root8 = TreeNode(5)
root8.right = TreeNode(5)
root8.right.right = TreeNode(5)
root8.right.right.right = TreeNode(5)
assert solution.findMode(root8) == [5]  # repeated chain

Test	Why
[1,null,2,2]	Validates duplicate counting and BST traversal
[0]	Tests smallest valid input
Unique values	Ensures all nodes become modes
All same values	Verifies repeated counting logic
Multiple modes	Confirms ties are handled correctly
Left-skewed tree	Tests unbalanced recursion
Negative values	Confirms support for full value range
Duplicate chain	Validates repeated consecutive counting

Edge Cases

Single Node Tree

A tree containing only one node is the smallest valid input. A buggy implementation might fail to initialize counters correctly or accidentally return an empty result. Our implementation handles this naturally because the first visited node sets current_count = 1, updates max_frequency, and becomes the first mode.

Every Value Is Unique

If every node contains a distinct value, every value appears exactly once. This means all values are modes. A common mistake is accidentally overwriting previous candidates instead of keeping ties. Our implementation correctly appends values whenever current_count == max_frequency.

Multiple Values Share the Highest Frequency

It is possible for several values to appear the same number of times. For example, both 1 and 3 may appear twice while all others appear once. An incorrect implementation may only return the first maximum value encountered. Our solution explicitly checks for equal frequencies and appends tied values to the result list.

All Nodes Have the Same Value

If every node contains the same value, the algorithm must avoid repeatedly appending duplicates to the mode list. Our implementation only replaces the modes list when a strictly higher frequency is found, ensuring the final result contains exactly one copy of the mode value.