Maximum Depth of N-ary Tree Solution Explained

Data Structures / Tree

Maximum Depth of N-ary Tree

Easy

Given a 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.

Problem Details

An N-ary tree is a tree where each node can have any number of children (not just 0, 1, or 2 like a binary tree). The depth is measured as the number of nodes from the root to the deepest leaf.

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

Output: 3



Explanation: The tree is:

        1

      / | \

    3  2  4

  / \

5   6



The longest path is 1 → 3 → 5 (or 6), which has 3 nodes.

Approach: Recursive DFS

The most intuitive approach uses recursion. For each node, we find the maximum depth among all its children, then add 1 for the current node.

Algorithm Steps

Base case: If the node is null, return 0
If the node has no children, return 1 (it's a leaf)
For each child, recursively calculate its depth
Return 1 + maximum depth among all children

Idea Map

Start at root node

Is node null? → Return 0

For each child in children:
depth = max(depth, dfs(child))

Return 1 + max_child_depth

Final depth value

Complexity Analysis

Time Complexity

O(n) - We visit each node exactly once, where n is the total number of nodes in the tree.

Space Complexity

O(h) - Recursion stack depth equals tree height. Worst case O(n) for skewed tree, O(log n) average for balanced.

Code


class Node:
Definition for an N-ary tree node.
    def __init__(self, val=None, children=None):
Constructor with optional value and children list.
        self.val = val
Store the node's value.
        self.children = children if children is not None else []
Store children list, default to empty list if None.


def maxDepth(root: 'Node') -> int:
Main function to find maximum depth of N-ary tree.
    if not root:
Base case: empty tree has depth 0.
        return 0
Return 0 for null root.
    
Empty line for readability.
    max_child_depth = 0
Initialize variable to track maximum depth among children.
    for child in root.children:
Iterate through each child of the current node.
        max_child_depth = max(max_child_depth, maxDepth(child))
Recursively find depth of each child and keep the maximum.
    
End of loop.
    return 1 + max_child_depth
Return current node (1) plus the maximum child depth.


class Node {
Definition for an N-ary tree node.
    public int val;
Node's integer value.
    public List<Node> children;
List of child nodes.
    public Node() {}
Default constructor.
    public Node(int _val) { val = _val; }
Constructor with value only.
    public Node(int _val, List<Node> _children) {
Full constructor with value and children.
        val = _val;
Assign value.
        children = _children;
Assign children list.
    }
End constructor.
}
End Node class.


public int maxDepth(Node root) {
Main method to find maximum depth.
    if (root == null) return 0;
Base case: null root has depth 0.
    int maxChildDepth = 0;
Track maximum depth among children.
    for (Node child : root.children) {
Iterate through each child.
        maxChildDepth = Math.max(maxChildDepth, maxDepth(child));
Recursively find child depth and keep maximum.
    }
End loop.
    return 1 + maxChildDepth;
Return current node depth plus max child depth.
}
End method.


class Node {
Definition for an N-ary tree node.
public:
Public access specifier.
    int val;
Node's integer value.
    vector<Node*> children;
Vector of child node pointers.
    Node() {}
Default constructor.
    Node(int _val) : val(_val) {}
Constructor with value using initializer list.
    Node(int _val, vector<Node*> _children) : val(_val), children(_children) {}
Full constructor with value and children.
};
End Node class.


int maxDepth(Node* root) {
Main function to find maximum depth.
    if (!root) return 0;
Base case: null pointer returns 0.
    int maxChildDepth = 0;
Track maximum depth among children.
    for (Node* child : root->children) {
Range-based for loop through children.
        maxChildDepth = max(maxChildDepth, maxDepth(child));
Recursively find child depth using std::max.
    }
End loop.
    return 1 + maxChildDepth;
Return current node depth plus max child depth.
}
End function.

Alternative: Iterative BFS

You can also solve this using BFS (level-order traversal). Count the number of levels as you traverse the tree.


def maxDepth(root):

    if not root: return 0

    queue = [root]

    depth = 0

    while queue:

        depth += 1

        for _ in range(len(queue)):

            node = queue.pop(0)

            queue.extend(node.children)

    return depth

Edge Cases & Common Mistakes

⚠️

Empty tree

If root is null, return 0 (not 1). The depth is measured in nodes, so an empty tree has 0 depth.

💡

Single node

A tree with only the root (no children) should return 1. Make sure your base case handles this correctly.

✓

N-ary vs Binary

Remember that N-ary trees can have any number of children, not just 2. Always iterate through all children.

📝

Iterative with queue

For BFS, use a queue and process nodes level by level. Increment depth after processing each level.

Understanding Recursion

This problem relies heavily on understanding recursion - breaking down a problem into smaller subproblems. Master recursion to solve tree problems efficiently.

Learn more about recursion →

lightbulb

Disclaimer: This problem is for educational purposes. Practice the 'Maximum Depth of N-ary Tree' problem on LeetCode.

AlgoExplained.dev