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.
1#include <vector>
2#include <queue>
3
4using namespace std;
5
6class Node {
7public:
8 int val;
9 vector<Node*> children;
10
11 Node() {}
12
13 Node(int _val) {
14 val = _val;
15 }
16
17 Node(int _val, vector<Node*> _children) {
18 val = _val;
19 children = _children;
20 }
21};
22
23class Solution {
24public:
25 vector<vector<int>> levelOrder(Node* root) {
26 vector<vector<int>> result;
27 if (!root) return result;
28
29 queue<Node*> q;
30 q.push(root);
31
32 while (!q.empty()) {
33 int levelSize = q.size();
34 vector<int> levelNodes;
35
36 for (int i = 0; i < levelSize; ++i) {
37 Node* node = q.front();
38 q.pop();
39 levelNodes.push_back(node->val);
40
41 for (Node* child : node->children) {
42 q.push(child);
43 }
44 }
45
46 result.push_back(levelNodes);
47 }
48
49 return result;
50 }
51};This C++ solution uses a standard queue to implement BFS for the n-ary tree. For each level, the queue stores all nodes to be processed, and their values are collected in the levelNodes list.
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.