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 <stdio.h>
2#include <stdlib.h>
3
4// Definition for a Node.
5struct Node {
6 int val;
7 int numChildren;
8 struct Node** children;
9};
10
11struct Node** queue;
12int head = 0, tail = 0;
13
14void enqueue(struct Node* node) {
15 queue[tail++] = node;
16}
17
18struct Node* dequeue() {
19 return queue[head++];
20}
21
22/**
23 * Note: The returned array must be malloced, assume caller calls free().
24 */
25int** levelOrder(struct Node* root, int** columnSizes, int* returnSize) {
26 if (!root) {
27 *returnSize = 0;
28 return NULL;
29 }
30
31 queue = (struct Node**)malloc(10000 * sizeof(struct Node*));
32 int** result = (int**)malloc(1000 * sizeof(int*));
33 *columnSizes = (int*)malloc(1000 * sizeof(int));
34 *returnSize = 0;
35
36 enqueue(root);
37
38 while (head < tail) {
39 int levelSize = tail - head;
40 result[*returnSize] = (int*)malloc(levelSize * sizeof(int));
41
42 for (int i = 0; i < levelSize; ++i) {
43 struct Node* node = dequeue();
44 result[*returnSize][i] = node->val;
45
46 for (int j = 0; j < node->numChildren; ++j) {
47 enqueue(node->children[j]);
48 }
49 }
50
51 (*columnSizes)[*returnSize] = levelSize;
52 (*returnSize)++;
53 }
54
55 free(queue);
56 return result;
57}This C code provides a manual implementation of a BFS for n-ary trees using basic arrays. A static array acts as a queue to track nodes for processing, with additional arrays for results and column sizes.
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.
1import java.util.*;
2
This Java solution incorporates a traverse helper function, examining each node recursively. If the current level hasn't yet been allocated a list, a new one is created. The node values are appended, and traversal proceeds to children with incremented depth, establishing lists dynamically as needed.