Maximum Depth of N-ary Tree - Practice Coding Problems

Maximum Depth of N-ary Tree - Problem

Given an n-ary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Note: Nary-Tree input serialization is represented in their level order traversal, each group of children is separated by the null value.

Input & Output

Example 1 — Standard N-ary Tree

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

› Output: 3

💡 Note: The tree has 3 levels: root (1) → children (3,2,4) → grandchildren (5,6). The maximum depth is 3.

Example 2 — Single Node

$ Input: root = [1]

› Output: 1

💡 Note: Tree has only the root node, so maximum depth is 1.

Example 3 — Linear Tree

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

› Output: 4

💡 Note: Each node has one child forming a linear chain: 1→2→3→4, depth is 4.

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input Tree

N-ary tree with nodes having multiple children

Find Paths

Identify all root-to-leaf paths

Count Max

Return length of longest path

Key Takeaway

🎯 Key Insight: Maximum depth is 1 + maximum depth among all child subtrees

Asked in

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

The key insight is that maximum depth equals 1 plus the maximum depth of any child subtree. Best approach is DFS recursion for its simplicity and clarity. Time: O(n), Space: O(h) where h is tree height.

Common Approaches

Approach	Time	Space	Notes
✓ Breadth-First Search	O(n)	O(w)	Level-order traversal counting levels until no more nodes
Brute Force DFS	O(n)	O(h)	Recursively explore all paths and track maximum depth
Optimized DFS	O(n)	O(h)	Clean recursive solution with early termination for leaves

Breadth-First Search — Algorithm Steps

Initialize queue with root and depth counter
While queue not empty, process current level
Add all children of current level to queue
Increment depth counter after each level

Visualization

Tap to expand

Step-by-Step Walkthrough

Level 1

Process root node

Level 2

Process all children of root

Level 3

Process grandchildren, count levels

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 Node* createNode(int val) {
    struct Node* node = (struct Node*)malloc(sizeof(struct Node));
    node->val = val;
    node->children = NULL;
    node->numChildren = 0;
    return node;
}

struct Queue* createQueue() {
    struct Queue* q = (struct Queue*)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 = (struct QueueNode*)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) {
    if (!root) {
        return 0;
    }
    
    struct Queue* queue = createQueue();
    enqueue(queue, root);
    int depth = 0;
    
    while (queue->size > 0) {
        depth++;
        int levelSize = queue->size;
        
        for (int i = 0; i < levelSize; i++) {
            struct Node* node = dequeue(queue);
            
            for (int j = 0; j < node->numChildren; j++) {
                enqueue(queue, node->children[j]);
            }
        }
    }
    
    return depth;
}

int main() {
    // For simplicity, we'll create a test case manually
    struct Node* root = createNode(1);
    struct Node* child1 = createNode(3);
    struct Node* child2 = createNode(2);
    struct Node* child3 = createNode(4);
    struct Node* child4 = createNode(5);
    struct Node* child5 = createNode(6);
    
    root->children = (struct Node**)malloc(3 * sizeof(struct Node*));
    root->children[0] = child1;
    root->children[1] = child2;
    root->children[2] = child3;
    root->numChildren = 3;
    
    child1->children = (struct Node**)malloc(2 * sizeof(struct Node*));
    child1->children[0] = child4;
    child1->children[1] = child5;
    child1->numChildren = 2;
    
    int result = solution(root);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Visit each node exactly once during level-order traversal

✓ Linear Growth

Space Complexity

O(w)

Queue stores maximum w nodes where w is maximum width of tree

✓ Linear Space

85.0K Views

Medium Frequency

~15 min Avg. Time

2.8K 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

Breadth-First Search — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler