Sponsored
Sponsored
This approach uses a queue data structure to perform a breadth-first search (BFS) or level order traversal of an n-ary tree. The primary idea is to process each node starting from the root by visiting all children of the current node(s) before moving on to the next level. This is achieved by maintaining a queue that temporarily holds nodes to be processed at the current level while enqueueing their children for the next level.
Time Complexity: O(n), where n is the number of nodes in the tree, since each node is visited once.
Space Complexity: O(n), as we store the entire tree in the queue and result list in the worst case.
1from collections import deque
2
3class Node:
4 def __init__(self, val=None, children=None):
5 self.val = val
6 self.children = children if children is not None else []
7
8class Solution:
9 def levelOrder(self, root: 'Node') -> List[List[int]]:
10 if not root:
11 return []
12
13 result = []
14 queue = deque([root])
15
16 while queue:
17 level_size = len(queue)
18 level_nodes = []
19
20 for _ in range(level_size):
21 current = queue.popleft()
22 level_nodes.append(current.val)
23
24 for child in current.children:
25 queue.append(child)
26
27 result.append(level_nodes)
28
29 return resultThis Python code defines a Node class to represent tree nodes and a Solution class with a levelOrder method for BFS traversal. A deque is used for the queue to facilitate O(1) pops from the front. The traversal iterates over each level, processes all nodes at the current level, and queues their children.
A recursive approach uses a helper function to traverse the tree by maintaining a reference to the current level. The approach relies on depth-first search (DFS) to record nodes in their respective levels. The helper function is invoked for each node, and levels are tracked by an accumulated list of lists.
Time Complexity: O(n), with n being the total node count since we visit each node exactly once.
Space Complexity: O(n), accounting for the recursive call stack and the result storage.
1class Node:
2 def __init__(
This recursive solution defines a helper function traverse that processes a node and records its value in the list associated with the current level. Recursion ensures that nodes are dealt with in a depth-first fashion, expanding each branch fully before moving to another sibling branch.