Problem 429

Abstract / Summary

Return the nodes of an n-ary tree level by level in a list of lists.

Note

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

Python 0429.py

class Solution:
    def levelOrder(self, root: 'Node') -> List[List[int]]:
        levels = defaultdict(list)

        def deeper(node, depth):
            if node:
                levels[depth].append(node.val)
                for i in node.children:
                    deeper(i, depth + 1)

        deeper(root, 0)

        for i in levels:
            yield levels[i]
14 lines | 386 bytes | submitted September 1, 2023 | GitHub   tab size 4 | low complexity

Difficulty

This problem is ranked as
easy medium hard

and has an acceptance rate of about 72% (500k+ submissions).

Typical patterns to solve this problem:
  • Breadth First Search
  • Tree
I solved 663 easy, 1250 medium and 309 hard problems

AI Disclaimer

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.
LeetCode profile | GitHub repo

Code Walkthrough

Overview

The provided implementation defines a Solution class with a levelOrder method that performs a breadth-first traversal of an N-ary tree and produces the node values grouped by depth. The method builds a mapping from depth to a list of values using a defaultdict, fills it via a depth-first recursive helper, and finally yields each level in order.

Key Steps

Initialization of the level container

levels = defaultdict(list)

A defaultdict of lists is created to store node values keyed by their depth. This choice eliminates the need for explicit existence checks before appending values, allowing the code to add entries for new depths on the fly.

Recursive depth-first population

def deeper(node, depth):
    if node:
        levels[depth].append(node.val)
        for i in node.children:
            deeper(i, depth + 1)

The inner function deeper receives a node and its current depth. If the node is not None, its value is appended to the list associated with the current depth. The function then iterates over the node’s children collection, invoking itself with an incremented depth. This recursion walks the entire tree, ensuring every node contributes to the appropriate level list.

Invocation of the recursion

deeper(root, 0)

The traversal starts at the supplied root with an initial depth of zero. If root is None, the conditional inside deeper prevents any further action, resulting in an empty levels mapping.

Generation of the output

for i in levels:
    yield levels[i]

After the mapping is populated, the method iterates over the keys of levels and yields each list of values. Because defaultdict preserves insertion order of keys (in Python 3.7+), the yielded levels appear in ascending depth order.

Edge Cases Handled

When the input tree is empty (root is None), the recursive helper immediately returns without modifying levels. Consequently, the subsequent loop over levels produces no output, which correctly represents an empty traversal result.

The algorithm also gracefully accommodates nodes with zero, one, or many children. The for loop over node.children simply iterates over an empty collection when a node has no children, avoiding any special-case code.

Depth values are generated dynamically; there is no assumption about the maximum depth of the tree. The defaultdict automatically creates a new list for any previously unseen depth, ensuring that arbitrarily deep trees are processed without additional bookkeeping.

Performance Optimizations

The use of a single recursive pass means each node is visited exactly once, avoiding redundant traversals. By appending values directly into the levels structure during the depth-first walk, the implementation sidesteps the need for a separate pass to reorganize nodes by depth.

Choosing defaultdict(list) removes the overhead of conditional checks for key existence before each append operation. This reduces branching and streamlines the inner loop that processes children.

Yielding the level lists rather than returning a fully materialized list of lists enables lazy consumption of the result. Callers can iterate over the generator and process each level as it becomes available, which can be advantageous when only a subset of levels is needed or when the result is streamed to another consumer.

Overall, the design balances simplicity with efficient use of Python’s built-in data structures, delivering a traversal that scales linearly with the number of nodes while keeping memory usage proportional to the breadth of the tree at any given depth.

written by openai gpt

ELI5 - Simplified Explanation

Imagine a big tree where each branch has its own little basket of treasures. This code is like a helper walking through the tree to organize all those treasures into rows.

First, the helper gets ready with a collection of empty boxes to keep things tidy. Then, the helper starts at the very top of the tree, which is the root, and looks inside to find a treasure. Every time a treasure is found, the helper puts it into the right box depending on how deep it is hidden from the top.

Because a tree has many branches, the helper goes on an adventure to visit every single branch. If a branch has more little branches below it, the helper keeps going down to find those treasures too, making sure to mark how deep each one is. Once every branch has been visited and all the treasures are sorted into their specific depth boxes, the helper opens the boxes one by one to show everyone what was found.

written by google gemini

Code Quality

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):
n = 27 | median = 7 | μ = 6.11 | σ = 1.73

Complexity Analysis

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
generated automatically

Other Solutions

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 Go TS
LeetcodeHelp C++ Java Python
Progiez C++ Java Python
github BigEggStudy C#
black-shadows C++
charles-wangkai Java
Dijkstra-Edu Java
DimitrisJim JS
everthis JS
fartem Ruby
fpdjsns C++
fsq C++
halfrost Go
JoshCrozier JS
keineahnung2345 C++
Krazune C++
lkwq007 Python
suxrobGM C#
varunu28 Java
vthwang Java
YuriSpiridonov Python
AlgoMonster C++, Python, Java, TypeScript
WalkCCC C++, Python, Java
leetcode.ca C++, Go, Java, Python, TypeScript
LeetcodeHelp C++, Java, Python
Progiez C++, Java, Python
BigEggStudy C#
black-shadows C++, C++
charles-wangkai Java
Dijkstra-Edu Java
DimitrisJim JavaScript
everthis JavaScript
fartem Ruby
fpdjsns C++
fsq C++
halfrost Go
JoshCrozier JavaScript
keineahnung2345 C++
Krazune C++
lkwq007 Python
suxrobGM C#
varunu28 Java
vthwang Java
YuriSpiridonov Python
36 links | 23 authors | 8 languages

Videos

4 videos   did my crawler come up with invalid videos ? drop me a line.

Similar Problems

4 similar problems

Solved On The Same Day

30 solutions   September 1, 2023

Extra

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