N-ary Tree Level Order Traversal - Practice Coding Problems

N-ary Tree Level Order Traversal - Problem

Given the root of an n-ary tree, return the level order traversal of its nodes' values.

Nary-Tree input serialization is represented in their level order traversal, each group of children is separated by the null value (See examples).

In level order traversal, we visit all nodes at depth 0, then all nodes at depth 1, then all nodes at depth 2, and so on. Within each level, nodes can be visited in any order.

Input & Output

Example 1 — Basic N-ary Tree

$ Input: root = [1,null,3,2,4,null,5,6]

› Output: [[1],[3,2,4],[5,6]]

💡 Note: Level 0 contains root node 1. Level 1 contains its children 3, 2, 4. Level 2 contains children of node 3: nodes 5 and 6.

Example 2 — Deeper Tree

$ Input: root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]

› Output: [[1],[2,3,4,5],[6,7,8,9,10],[11,12,13],[14]]

💡 Note: Each level contains all nodes at that depth. The tree has 5 levels with varying numbers of nodes per level.

Example 3 — Single Node

$ Input: root = [1]

› Output: [[1]]

💡 Note: Tree with only root node results in single level containing just that node.

Constraints

The height of the n-ary tree is less than or equal to 1000
The total number of nodes is between [0, 10⁴]

Visualization

Tap to expand

Understanding the Visualization

Input Tree

N-ary tree with nodes having 0 or more children

Level Processing

Group nodes by their depth level

Output Array

2D array with each level as a separate sub-array

Key Takeaway

🎯 Key Insight: Use BFS queue to naturally process nodes level by level, collecting each complete level before moving to the next

Asked in

A Amazon 15 F Facebook 12 M Microsoft 10 G Google 8

The optimal approach uses BFS with a queue to naturally process nodes level by level. The key insight is that a queue processes nodes in the exact order needed for level-order traversal. Time: O(n), Space: O(w) where w is maximum tree width.

Common Approaches

Approach	Time	Space	Notes
✓ BFS Queue Traversal	O(n)	O(w)	Use a queue to process nodes level by level
Recursive DFS with Level Tracking	O(n)	O(h)	Use DFS to traverse the tree while tracking the current level

BFS Queue Traversal — Algorithm Steps

Add root to queue
While queue not empty, process all nodes at current level
Add children of current level nodes to queue for next level

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Add root to queue, start processing

Process Level

Process all nodes in current level, add their children

Next Level

Queue now contains next level nodes

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct Node {
    int val;
    struct Node** children;
    int numChildren;
};

struct QueueNode {
    struct Node* node;
    struct QueueNode* next;
};

struct Queue {
    struct QueueNode* front;
    struct QueueNode* rear;
    int size;
};

struct Queue* createQueue() {
    struct Queue* q = malloc(sizeof(struct Queue));
    q->front = q->rear = NULL;
    q->size = 0;
    return q;
}

void enqueue(struct Queue* q, struct Node* node) {
    struct QueueNode* temp = malloc(sizeof(struct QueueNode));
    temp->node = node;
    temp->next = NULL;
    
    if (q->rear == NULL) {
        q->front = q->rear = temp;
    } else {
        q->rear->next = temp;
        q->rear = temp;
    }
    q->size++;
}

struct Node* dequeue(struct Queue* q) {
    if (q->front == NULL) return NULL;
    
    struct QueueNode* temp = q->front;
    struct Node* node = temp->node;
    q->front = q->front->next;
    
    if (q->front == NULL) {
        q->rear = NULL;
    }
    
    free(temp);
    q->size--;
    return node;
}

int** solution(struct Node* root, int* returnSize, int** returnColumnSizes) {
    *returnSize = 0;
    if (!root) return NULL;
    
    int** result = malloc(1000 * sizeof(int*));
    *returnColumnSizes = malloc(1000 * sizeof(int));
    
    struct Queue* queue = createQueue();
    enqueue(queue, root);
    
    while (queue->size > 0) {
        int levelSize = queue->size;
        int* currentLevel = malloc(levelSize * sizeof(int));
        
        // Process all nodes at current level
        for (int i = 0; i < levelSize; i++) {
            struct Node* node = dequeue(queue);
            currentLevel[i] = node->val;
            
            // Add all children to queue for next level
            for (int j = 0; j < node->numChildren; j++) {
                enqueue(queue, node->children[j]);
            }
        }
        
        result[*returnSize] = currentLevel;
        (*returnColumnSizes)[*returnSize] = levelSize;
        (*returnSize)++;
    }
    
    free(queue);
    return result;
}

int main() {
    // Simplified for basic testing
    printf("[[1],[3,2,4],[5,6]]\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Visit each node exactly once

✓ Linear Growth

Space Complexity

O(w)

Queue stores maximum width w of tree at any level, plus O(n) for result

✓ Linear Space

125.0K Views

Medium Frequency

~15 min Avg. Time

3.4K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

BFS Queue Traversal — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler