Abstract / Summary

Find the value or values that appear most frequently in a binary search tree.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 59% (600k+ submissions).

Typical patterns to solve this problem:

• Binary Search Tree
• Binary Tree
• Depth First Search
• Tree

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation defines a Solution class with a method findMode that computes the mode(s) of a binary search tree (BST). The method traverses the entire tree, records the frequency of each value, determines the highest frequency, and returns all values that appear with that frequency. The code is concise, leverages Python’s standard library for counting, and performs the required work in a single depth-first pass.

Key Steps

The algorithm can be broken down into three logical phases: initialization of the frequency container, recursive traversal to populate frequencies, and extraction of the mode values.

The first phase creates a defaultdict that automatically initializes missing keys to zero, allowing direct increment operations without explicit existence checks.

freq = defaultdict(int)

The second phase defines a nested helper function deeper that performs a pre-order depth-first traversal. For each visited node, the node’s value is used as a key in freq, and its count is incremented. The function then recurses on the left and right children.

def deeper(node):
    if node:
        freq[node.val] += 1
        deeper(node.left)
        deeper(node.right)

The traversal is initiated with the root of the tree.

deeper(root)

The final phase computes the maximum frequency observed across all values and builds a list of keys whose count matches this maximum. The max function scans the dictionary’s values to find the highest count, and a list comprehension filters the keys accordingly.

mode = max(freq.values())
return [i for i in freq if freq[i] == mode]

Edge Cases

The implementation gracefully handles several edge conditions without additional branching logic. When the input tree is empty (root is None), the recursive helper never enters the body of the if node: block, leaving freq empty. The subsequent call to max(freq.values()) would raise a ValueError in a typical scenario, but the problem constraints guarantee at least one node, so this situation is implicitly excluded. For a tree consisting of a single node, the traversal records a single entry with a count of one, max returns one, and the list comprehension returns a list containing that sole value. If all nodes share the same value, the frequency dictionary contains a single key with a count equal to the total number of nodes; the list comprehension yields a list with that one value, correctly identifying it as the sole mode. When multiple distinct values share the highest frequency, the dictionary holds each with the same count, and the list comprehension returns all such values, preserving the requirement to return every mode.

Performance Optimizations

The code achieves efficiency through several deliberate choices. Using defaultdict(int) eliminates the need for explicit key existence checks, allowing each increment operation to run in constant time. The recursive deeper function performs a single pass over the tree, visiting each node exactly once, which minimizes overhead compared to approaches that might traverse the structure multiple times. By postponing the determination of the maximum frequency until after the full traversal, the algorithm avoids repeated scans of the frequency map during node processing. The final list comprehension constructs the result in a single expression, iterating over the dictionary keys only once to filter those matching the pre-computed maximum, thereby avoiding additional passes or temporary collections. These design decisions collectively keep the runtime low and the memory footprint limited to the frequency map and the result list.

Imagine a very large tree where every single branch has a number hanging on it. The goal is to walk through the entire tree and write down every number encountered in a notebook.

A special dictionary is created to keep track of these numbers. Every time a number appears, a little mark goes next to it in the notebook to count how many times it was seen.

The journey starts at the very top of the branch structure. A small helper function acts like a curious explorer. It looks at the current branch, writes the number in the notebook, and then scurries off to look at the branches attached to the left and the right. This keeps happening until every single branch has been visited.

Once the entire tree has been explored, the notebook shows how many times each number was found. The next step is to look at all those counting marks and find the highest number of marks any specific digit received.

Lastly, a search happens through the notebook to pick out all the numbers that share that highest count. These are the most popular numbers from the tree.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: linear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Java	Python						TS
	WalkCCC	C++	Java	Python
	leetcode.ca	C++	Java	Python		C#			Go
	LeetcodeHelp	C++	Java	Python
	MemoryLimitExceeded	C++		Python
	Progiez	C++	Java	Python
github	BigEggStudy					C#
	black-shadows	C++
	charles-wangkai		Java
	everthis				JS
	fartem							Ruby
	fsq	C++
	JoshCrozier				JS
	keineahnung2345	C++
	linouk23	C++
	lkwq007			Python
	ruoru						Rust
	suxrobGM					C#
	varunu28		Java
	vthwang		Java
	wisdompeak	C++
	YuriSpiridonov			Python
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, C#, Go, Java, Python
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fartem	Ruby
fsq	C++
JoshCrozier	JavaScript
keineahnung2345	C++
linouk23	C++
lkwq007	Python
ruoru	Rust
suxrobGM	C#
varunu28	Java
vthwang	Java
wisdompeak	C++
YuriSpiridonov	Python
zfang399	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality