Abstract / Summary

For each level of a binary tree, find the largest value among all nodes at that level.

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 66% (700k+ submissions).

Typical patterns to solve this problem:

• Binary Tree
• Breadth First Search
• 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 class with two methods that together compute the largest value at each depth of a binary tree. The largestValues method prepares a dictionary to store the maximum value per depth, invokes a depth-first traversal, and then extracts the results in order of increasing depth. The traversal logic resides in the helper method deeper, which updates the dictionary while recursively visiting left and right children.

Key Steps

Initialization of the accumulator

self.maximum = {}

A fresh dictionary is created for each call to largestValues. The keys represent depth levels (starting at 0) and the values hold the current maximum encountered at that level.

Recursive depth-first traversal

def deeper(self, root, depth):
    if not root:
        return

    if not depth in self.maximum:
        self.maximum[depth] = root.val
    else:
        self.maximum[depth] = max(self.maximum[depth], root.val)

    if root.left:
        self.deeper(root.left, depth + 1)
    if root.right:
        self.deeper(root.right, depth + 1)

The method receives a node and its depth. It first checks for a null node, which terminates that branch of recursion. For a non-null node, it either creates a new entry for the current depth or updates the existing entry with the larger of the stored value and the node’s value. The recursion proceeds to the left child, then the right child, each time incrementing the depth counter.

Collection of results in depth order

result = []
i = 0
while i in self.maximum:
    result.append(self.maximum[i])
    i += 1
return result

After the traversal finishes, a simple loop walks through consecutive integer depths starting at zero. As long as a depth key exists in the dictionary, its associated maximum is appended to the result list. The loop stops when a depth is missing, guaranteeing that the output list contains values for all depths present in the tree, ordered from root to deepest leaf.

Edge Cases Handled

When the input tree is empty (root is None), the initial call to deeper immediately returns without modifying the dictionary. Consequently, the while-loop in largestValues finds no keys and returns an empty list, correctly representing the absence of any depth levels.

A tree consisting of a single node triggers the creation of a dictionary entry for depth 0 with that node’s value. The subsequent loop extracts this single entry, yielding a list of length one.

Unbalanced trees, where one subtree is deeper than the other, are naturally accommodated. The recursion explores every reachable node, and the dictionary grows only for depths that actually appear. The final extraction loop stops precisely at the deepest existing depth, ignoring any gaps that could arise from irregular structures.

Performance Optimizations

The algorithm uses a single mutable dictionary (self.maximum) that is updated in-place during the traversal. This avoids the overhead of constructing intermediate collections for each depth level. The use of the built-in max function provides a fast comparison for updating the stored maximum.

Recursion proceeds depth-first, which means each node is visited exactly once and the call stack depth mirrors the tree height. The result construction iterates over consecutive integer keys, which is more efficient than sorting the dictionary keys because the keys are naturally contiguous from zero up to the maximum depth.

By separating the traversal from the result assembly, the code keeps the critical path (node visitation and maximum update) minimal and free of additional data-structure manipulations, leading to a streamlined execution flow.

Imagine a big tree standing upside down with its roots at the very top. Each spot on the tree has a special number written on it. The goal is to walk down every single branch to find the biggest number waiting on each floor of the tree.

The first part of the code acts like a tiny explorer who starts at the top. The explorer checks which floor they are on and looks at the number there. If the explorer has never been to that floor before, they remember that number. If the explorer has been there before, they compare the new number to the one they already remembered and keep the bigger one. After checking the current spot, the explorer continues down to the left side and then the right side to see if there are more numbers to find on the next floor.

The second part of the code sets up a blank notepad to start writing down the biggest numbers. It tells the explorer to go visit the tree, starting right at the top. Once the explorer finishes visiting every branch and reporting back, the code looks at its notepad. It reads through the floors one by one and puts all those biggest numbers into a neat row so they are easy to see.

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			Rust		Go			TS
	LeetcodeHelp	C++	Java	Python
	MemoryLimitExceeded	C++		Python
	Progiez	C++	Java	Python
github	BigEggStudy					C#
	black-shadows	C++
	charles-wangkai		Java
	DimitrisJim										C
	everthis				JS
	fartem							Ruby
	fengvyi	C++
	gouthampradhan		Java
	halfrost								Go
	JoshCrozier				JS
	keineahnung2345	C++
	Krazune	C++
	linouk23	C++
	lkwq007			Python
	MacJim	C++
	ruoru						Rust
	Shamik07									Dart
	suxrobGM					C#
	varunu28		Java
	YuriSpiridonov			Python
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, Rust, TypeScript
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
DimitrisJim	C
everthis	JavaScript
fartem	Ruby
fengvyi	C++
gouthampradhan	Java
halfrost	Go
JoshCrozier	JavaScript
keineahnung2345	C++
Krazune	C++
linouk23	C++
lkwq007	Python
MacJim	C++
ruoru	Rust
Shamik07	Dart
suxrobGM	C#
varunu28	Java
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