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.
1import java.util.*;
2
3class Node {
4 public int val;
5 public List<Node> children;
6
7 public Node() {}
8
9 public Node(int _val) {
10 val = _val;
11 }
12
13 public Node(int _val, List<Node> _children) {
14 val = _val;
15 children = _children;
16 }
17}
18
19class Solution {
20 public List<List<Integer>> levelOrder(Node root) {
21 List<List<Integer>> result = new ArrayList<>();
22 if (root == null) return result;
23
24 Queue<Node> queue = new LinkedList<>();
25 queue.add(root);
26
27 while (!queue.isEmpty()) {
28 int levelSize = queue.size();
29 List<Integer> levelNodes = new ArrayList<>();
30
31 for (int i = 0; i < levelSize; i++) {
32 Node current = queue.poll();
33 levelNodes.add(current.val);
34
35 if (current.children != null) {
36 queue.addAll(current.children);
37 }
38 }
39
40 result.add(levelNodes);
41 }
42
43 return result;
44 }
45}This Java code defines a Node class and a Solution class where the levelOrder method traverses the n-ary tree using a queue implemented with a LinkedList. Nodes are processed level by level, and each node's value is added to the current level list before their children are queued for the next level.
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.