Abstract / Summary

Return the values of a binary tree's nodes level by level from top to bottom.

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 73% (4+ million submissions).

Typical patterns to solve this problem:

• Binary Tree
• Breadth 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 performs a breadth-first (level order) traversal of a binary tree and returns the node values grouped by depth. It uses a depth-first recursion to populate a mapping from depth to a list of values, then extracts the groups in order of increasing depth.

Key Steps

The algorithm begins by creating a dictionary that automatically creates an empty list for any new depth key.

levels = defaultdict(list)

A nested helper function named deeper is defined to walk the tree recursively. The function receives a node and its current depth. If the node exists, its value is appended to the list associated with that depth, and the function recurses on the left and right children, each time incrementing the depth by one.

def deeper(node, depth):
    if node:
        levels[depth].append(node.val)
        deeper(node.left,  depth+1)
        deeper(node.right, depth+1)

The recursion is initiated with the root node and a starting depth of zero.

deeper(root, 0)

After the entire tree has been visited, the dictionary keys (depth levels) are sorted, and the corresponding value lists are collected into the final result list.

return [ levels[l] for l in sorted(levels.keys()) ]

Edge Cases Handled

When the input tree is empty (root is None), the recursive helper is called with a None node. The guard if node: prevents any further processing, leaving the levels dictionary empty. Consequently, the sorted key list is empty and the function returns an empty list, which correctly represents the level order of an empty tree.

The recursion naturally accommodates trees that are highly unbalanced, such as a chain of left children or right children. Each recursive call increments the depth, so even a tree of depth n will produce n distinct entries in the levels dictionary without special casing.

Because the helper appends values before recursing on children, nodes are recorded in left-to-right order for each level, matching the conventional definition of level order traversal.

Performance Optimizations

The use of defaultdict(list) eliminates the need to check whether a depth key already exists before appending a value. This reduces conditional overhead during the traversal.

The algorithm performs a single depth-first pass over the tree, visiting each node exactly once. By collecting values during the recursive descent, it avoids the need for an auxiliary queue that a typical iterative breadth-first approach would require.

Sorting of the depth keys occurs only after the entire traversal is complete. Since the number of distinct depths equals the height of the tree, the sorting step operates on a relatively small collection compared with the total number of nodes, minimizing its impact on overall runtime.

Overall, the combination of a recursive walk, automatic list creation, and deferred sorting yields an implementation that is concise and efficient for the level order traversal task.

Imagine a group of friends standing on different steps of a long staircase. The top step is called level zero, the next one down is level one, and so on. This code is like a helper who walks through the whole staircase to visit every friend.

The helper starts at the very top. Whenever the helper finds a friend, the helper looks at which step that friend is standing on and writes their name down on a list for that specific level.

After visiting a friend, the helper looks to see if there is someone standing to the left or to the right on the next step down. If there is, the helper travels to that friend and does the exact same thing again. This keeps happening in a repeating loop until every single friend on every single step has been visited.

Once the helper has finished visiting everyone, all the lists are put in order from the top step to the bottom step so that the final collection shows everyone organized by exactly where they were standing.

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

not analyzed yet

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++	Python	Java					TS
	WalkCCC	C++	Python	Java
	leetcode.ca	C++	Python	Java		JS		Rust	TS				Go
	LeetcodeHelp	C++	Python	Java
	MemoryLimitExceeded	C++	Python
	Progiez	C++	Python	Java
github	AdelDaniel													Dart
	aylei							Rust
	begeekmyfriend						C
	BigEggStudy				C#
	black-shadows	C++
	bujosa		Python
	charles-wangkai			Java
	chenyanzhe	C++
	Dijkstra-Edu			Java
	DimitrisJim					JS
	everthis					JS
	fartem										Ruby
	FelixFan1122				C#
	fengvyi	C++
	fpdjsns		Python
	gaosq0604		Python
	Garvit244		Python
	halfrost												Go
	haoel	C++
	JoshCrozier					JS
	keineahnung2345	C++
	Krazune	C++
	lennylxx						C
	linouk23	C++
	lkwq007		Python
	luangong	C++							TS
	MacJim	C++
	martianoff									Scala
	qiyuangong		Python
	ruoru							Rust
	shreymehul				C#
	sonugiri1043	C++
	suxrobGM				C#
	trung-hn		Python
	varunu28			Java
	vli02						C
	vthwang			Java
	XiaotaoGuo	C++
	yuanliu666											Kotlin
	YuriSpiridonov		Python
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, JavaScript, Python, Rust, TypeScript
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
AdelDaniel	Dart
aylei	Rust
begeekmyfriend	C
BigEggStudy	C#
black-shadows	C++, C++
bujosa	Python
charles-wangkai	Java
chenyanzhe	C++
Dijkstra-Edu	Java
DimitrisJim	JavaScript
everthis	JavaScript
fartem	Ruby
FelixFan1122	C#
fengvyi	C++
fpdjsns	Python
gaosq0604	Python
Garvit244	Python
halfrost	Go
haoel	C++
JoshCrozier	JavaScript
keineahnung2345	C++
Krazune	C++
lennylxx	C
linouk23	C++
lkwq007	Python
luangong	C++, TypeScript
MacJim	C++
martianoff	Scala
qiyuangong	Python
ruoru	Rust
shreymehul	C#
sonugiri1043	C++
suxrobGM	C#
trung-hn	Python
varunu28	Java
vli02	C
vthwang	Java
XiaotaoGuo	C++
yuanliu666	Kotlin
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