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]
Difficulty
and has an acceptance rate of about 72% (500k+ submissions).
Typical patterns to solve this problem:
- Breadth First Search
- Tree
AI Disclaimer
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.
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.
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.
Code Quality
Complexity Analysis
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
Other Solutions
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 |
Videos
Similar Problems
- problem 102: Binary Tree Level Order Traversal
- problem 589: N-ary Tree Preorder Traversal
- problem 590: N-ary Tree Postorder Traversal
- problem 2039: The Time When the Network Becomes Idle
Solved On The Same Day
- problem 144: Binary Tree Preorder Traversal
- problem 145: Binary Tree Postorder Traversal
- problem 222: Count Complete Tree Nodes
- problem 404: Sum of Left Leaves
- problem 501: Find Mode in Binary Search Tree
- problem 543: Diameter of Binary Tree
- problem 559: Maximum Depth of N-ary Tree
- problem 589: N-ary Tree Preorder Traversal
- problem 590: N-ary Tree Postorder Traversal
- problem 637: Average of Levels in Binary Tree
- problem 700: Search in a Binary Search Tree
- problem 703: Kth Largest Element in a Stream
- problem 79: Word Search
- problem 81: Search in Rotated Sorted Array II
- problem 97: Interleaving String
- problem 99: Recover Binary Search Tree
- problem 173: Binary Search Tree Iterator
- problem 199: Binary Tree Right Side View
- problem 230: Kth Smallest Element in a BST
- problem 235: Lowest Common Ancestor of a Binary Search Tree
- problem 341: Flatten Nested List Iterator
- problem 508: Most Frequent Subtree Sum
- problem 513: Find Bottom Left Tree Value
- problem 538: Convert BST to Greater Tree
- problem 65: Valid Number
- problem 85: Maximal Rectangle
- problem 87: Scramble String
- problem 126: Word Ladder II
- problem 127: Word Ladder
Extra
- 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