LeetCode 559 - Maximum Depth of N-ary Tree

Difficulty: 🟢 Easy
Topics: Tree, Depth-First Search, Breadth-First Search

Solution

Problem Understanding

The problem asks us to compute the maximum depth of an n-ary tree. An n-ary tree is a tree where each node can have zero or more children, unlike a binary tree where each node has at most two children.

The depth of a tree is defined as the number of nodes along the longest path from the root node to any leaf node. A leaf node is a node that has no children.

We are given the root node of the tree, and we must return an integer representing the maximum depth.

For example, consider the tree:

The longest path from the root to a leaf is:

1 -> 3 -> 5

This path contains 3 nodes, so the maximum depth is 3.

The input serialization shown in the problem statement uses level-order traversal with null separators to indicate groups of children. However, when solving the problem on LeetCode, we do not need to parse this serialization ourselves. We are directly given the root node of the constructed tree.

The constraints tell us several important things:

The tree can contain up to 10^4 nodes.
The depth can be as large as 1000.

This means the algorithm must be efficient enough to process thousands of nodes without unnecessary repeated work.

Several edge cases are important:

The tree may be empty, meaning root is None or nil.
The tree may contain only a single node.
The tree may be highly unbalanced, forming a chain of depth 1000.
Some nodes may have many children while others have none.

A correct solution must handle all of these scenarios safely and efficiently.

Approaches

A brute-force idea would be to repeatedly compute the depth of every subtree independently. For each node, we could recursively compute the depth of each child subtree and compare them, but without careful organization this could lead to repeated calculations of the same subtrees multiple times.

Although this eventually produces the correct answer, it is inefficient because the same branches may be traversed repeatedly. In the worst case, the time complexity can grow significantly larger than necessary.

The key observation for an optimal solution is that the depth of a node depends only on the maximum depth among its children.

For any node:

If it has no children, its depth is 1.
Otherwise, its depth is:

1 + maximum depth among all children

This naturally suggests a depth-first search traversal. We recursively compute the depth of each child exactly once, then use those results to compute the current node's depth.

Because every node is visited only once, the solution is optimal.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(N²)	O(H)	Recomputes subtree depths multiple times
Optimal DFS	O(N)	O(H)	Visits each node exactly once

Here:

N is the number of nodes
H is the height of the tree

Algorithm Walkthrough

Recursive Depth-First Search

Start at the root node.

The root represents the top of the tree. If the root is None, the tree is empty, so the maximum depth is 0. 2. Check whether the current node has children.

If a node has no children, it is a leaf node. A leaf contributes a depth of 1 because the path contains only the node itself. 3. Recursively compute the depth of every child.

For each child node, call the same function again. This breaks the large problem into smaller subproblems. 4. Track the maximum child depth.

Among all child subtrees, we only care about the deepest one because the problem asks for the longest root-to-leaf path. 5. Add 1 for the current node.

Once the deepest child depth is known, include the current node itself in the path length. 6. Return the computed depth upward.

Each recursive call returns the maximum depth of its subtree to its parent.

Why it works

The algorithm works because every subtree is solved correctly before its parent node computes its own depth. This is a classic recursive tree property.

For every node:

depth(node) = 1 + max(depth(child))

Since leaf nodes correctly return 1, and every parent builds upon correct child answers, the recursion guarantees that the root ultimately receives the correct maximum depth of the entire tree.

Python Solution

"""
# Definition for a Node.
class Node:
    def __init__(self, val: Optional[int] = None, children: Optional[List['Node']] = None):
        self.val = val
        self.children = children
"""

from typing import List, Optional

class Solution:
    def maxDepth(self, root: 'Node') -> int:
        if root is None:
            return 0

        if not root.children:
            return 1

        max_child_depth = 0

        for child in root.children:
            child_depth = self.maxDepth(child)
            max_child_depth = max(max_child_depth, child_depth)

        return 1 + max_child_depth

The implementation begins by handling the empty tree case. If root is None, there are no nodes, so the depth is 0.

Next, the code checks whether the current node has children. If not, the node is a leaf node and contributes a depth of 1.

The variable max_child_depth stores the largest subtree depth found among all children. The loop iterates through every child and recursively computes its depth.

For each child:

child_depth = self.maxDepth(child)

This recursively solves the same problem for the child subtree.

The maximum value is tracked using:

max(max_child_depth, child_depth)

Finally, the algorithm returns:

1 + max_child_depth

The extra 1 accounts for the current node itself.

Go Solution

/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Children []*Node
 * }
 */

func maxDepth(root *Node) int {
    if root == nil {
        return 0
    }

    if len(root.Children) == 0 {
        return 1
    }

    maxChildDepth := 0

    for _, child := range root.Children {
        childDepth := maxDepth(child)

        if childDepth > maxChildDepth {
            maxChildDepth = childDepth
        }
    }

    return 1 + maxChildDepth
}

The Go implementation follows the same recursive structure as the Python version.

The primary difference is how Go handles missing values and collections:

Go uses nil instead of None
Child nodes are stored in a slice: []*Node
The length of the children slice is checked using len(root.Children)

Go does not provide a built-in max() function for integers, so the comparison is written manually using an if statement.

Since the maximum depth is at most 1000, integer overflow is not a concern in Go.

Worked Examples

Example 1

Input:

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

Tree:

Step-by-step DFS traversal

Current Node	Child Depths	Returned Depth
5	none	1
6	none	1
3	max(1, 1)	2
2	none	1
4	none	1
1	max(2, 1, 1)	3

Final answer:

The longest path is:

1 -> 3 -> 5

Example 2

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]

The deepest branch is:

1 -> 3 -> 7 -> 11 -> 14

DFS Trace

Current Node	Returned Depth
14	1
11	2
7	3
3	4
1	5

Final answer:

Complexity Analysis

Measure	Complexity	Explanation
Time	O(N)	Every node is visited exactly once
Space	O(H)	Recursive call stack stores one frame per tree level

The time complexity is linear because each node participates in exactly one recursive call.

The space complexity depends on the recursion depth. In the worst case, the tree could become completely skewed, causing the recursion stack to grow to height H. Since the maximum depth is bounded by 1000, this remains manageable.

Test Cases

# Definition for testing
class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children or []

class Solution:
    def maxDepth(self, root):
        if root is None:
            return 0

        if not root.children:
            return 1

        max_child_depth = 0

        for child in root.children:
            max_child_depth = max(
                max_child_depth,
                self.maxDepth(child)
            )

        return 1 + max_child_depth

solution = Solution()

# Empty tree
assert solution.maxDepth(None) == 0  # tree has no nodes

# Single node
root = Node(1)
assert solution.maxDepth(root) == 1  # only root exists

# Example 1
root = Node(1, [
    Node(3, [
        Node(5),
        Node(6)
    ]),
    Node(2),
    Node(4)
])
assert solution.maxDepth(root) == 3  # standard multi-child tree

# Deep chain
root = Node(1, [
    Node(2, [
        Node(3, [
            Node(4)
        ])
    ])
])
assert solution.maxDepth(root) == 4  # highly unbalanced tree

# Wide tree
root = Node(1, [
    Node(2),
    Node(3),
    Node(4),
    Node(5),
    Node(6)
])
assert solution.maxDepth(root) == 2  # many children but shallow

# Uneven subtree depths
root = Node(1, [
    Node(2),
    Node(3, [
        Node(4, [
            Node(5)
        ])
    ])
])
assert solution.maxDepth(root) == 4  # longest branch determines answer

Test	Why
Empty tree	Verifies handling of `None` root
Single node	Smallest non-empty tree
Example 1	Validates standard branching structure
Deep chain	Tests recursion depth behavior
Wide tree	Ensures breadth does not affect correctness
Uneven subtree depths	Confirms algorithm chooses deepest path

Edge Cases

Empty Tree

An empty tree occurs when root is None or nil. This case is easy to overlook because recursion usually assumes at least one node exists.

If this case is not handled explicitly, the implementation may attempt to access root.children, causing a runtime error.

The solution safely handles this by immediately returning:

if root is None:
    return 0

This correctly represents that an empty tree has depth 0.

Single Node Tree

A tree containing only the root node is another important edge case. Since the root has no children, it is also a leaf node.

A buggy implementation might incorrectly return 0 if it only counts edges instead of nodes.

The solution correctly returns 1 because the path contains exactly one node.

Highly Unbalanced Tree

An n-ary tree can degenerate into a linked list where every node has exactly one child.

Example:

1 -> 2 -> 3 -> 4 -> 5

This stresses recursion depth and ensures the algorithm properly follows a single deep branch.

The implementation handles this naturally because each recursive call processes exactly one child until reaching the leaf node.

Nodes With Empty Children Lists

Some implementations incorrectly assume every node has children.

In this problem, leaf nodes may have:

children = []

The solution safely checks:

if not root.children:

This works correctly for empty lists and properly identifies leaf nodes.