LeetCode 559: Maximum Depth of N-ary Tree Solution in Python – A Step-by-Step Guide

What Is LeetCode 559: Maximum Depth of N-ary Tree?

In LeetCode 559: Maximum Depth of N-ary Tree, you’re given the root of an N-ary tree, where each node can have any number of children (stored as a list), and your task is to return the maximum depth—the length of the longest path from root to a leaf, measured as the number of nodes along that path. For example, with a tree where the root has children [5, 6], and 5 has children [3, 2, 4], the maximum depth is 3 (root → 5 → any of 3, 2, 4). This problem builds on LeetCode 104: Maximum Depth of Binary Tree but generalizes to N-ary trees with flexible child counts.

Problem Statement

• Input: root (Node)—root of an N-ary tree.
• Output: Integer—maximum depth (number of nodes from root to deepest leaf).
• Rules: Depth is the longest root-to-leaf path; each node has a value and list of children.

Constraints

• Number of nodes: 0 to 10⁴.
• 0 <= len(node.children) <= 10⁴ per node.
• Node values: -100 to 100.

Examples

• Input: root = [1,null,3,2,4,null,5,6]
• Output: 3
• Tree:
``` 1 /|\ 3 2 4 / \ 5 6 ```
• Depth: 1 → 3 → 5 or 6 = 3.
• 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: 5
• Depth: 1 → 4 → 8 → 11 → 14 = 5.
• Input: root = []
• Output: 0
• Empty tree.

Understanding the Problem: Measuring Tree Depth

To solve LeetCode 559: Maximum Depth of N-ary Tree in Python, we need to find the longest path from the root to any leaf in an N-ary tree, counting nodes along the way. Unlike binary trees with fixed left and right children, N-ary trees have a dynamic list of children, requiring us to consider all paths through multiple branches. A naive approach might manually trace every path (exponential), but with up to 10⁴ nodes, recursive or iterative traversal is ideal. We’ll explore:

• Best Solution (Recursive DFS): O(n) time, O(h) space (n = nodes, h = height)—simple and efficient.
• Alternative Solution (Iterative BFS): O(n) time, O(w) space (w = max width)—level-based and thorough.

Let’s dive into the recursive solution with a friendly breakdown!

Best Solution: Recursive DFS

Why Recursive DFS Wins

The recursive DFS is the best for LeetCode 559 because it computes the maximum depth in O(n) time and O(h) space (h = tree height) by traversing the tree once, recursively calculating the depth of each subtree and taking the maximum across all children at each node. It’s like climbing down every branch of the family tree, measuring how far you go, and reporting the deepest dive—all with a simple, elegant function!

How It Works

Think of this as a tree-depth explorer:

• Step 1: Base Case:
• If root is None, return 0 (empty tree).
• Step 2: Recursive Depth:
• For each child, recursively compute its subtree depth.
• Step 3: Max Depth:
• Take max depth among all children, add 1 for current node.
• Step 4: Handle No Children:
• If no children, depth is 1 (leaf node).
• Step 5: Return Result:
• Maximum depth from root.
• Why It Works:
• DFS naturally explores all paths to leaves.
• Max aggregation ensures longest path.

It’s like a tree-depth measurer!

Step-by-Step Example

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

• Step 1: Root = 1, children = [3, 2, 4].
• Step 2: DFS on children:
• Node 3: Children = [5, 6].
• DFS(5): No children, depth = 1.
• DFS(6): No children, depth = 1.
• Max = 1, Depth = 1 + 1 = 2.
• Node 2: No children, depth = 1.
• Node 4: No children, depth = 1.
• Step 3: Root max = max(2, 1, 1) = 2, Depth = 2 + 1 = 3.
• Result: 3.

Example: root = [1,null,2]

• Step 1: Root = 1, children = [2].
• Step 2: DFS(2): No children, depth = 1.
• Step 3: Max = 1, Depth = 1 + 1 = 2.
• Result: 2.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained for beginners:

class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children if children is not None else []

class Solution:
    def maxDepth(self, root: 'Node') -> int:
        # Step 1: Base case - empty tree
        if not root:
            return 0

        # Step 2: Handle leaf node or recurse on children
        if not root.children:
            return 1

        # Step 3: Recursively get max depth of each child
        max_child_depth = 0
        for child in root.children:
            child_depth = self.maxDepth(child)
            max_child_depth = max(max_child_depth, child_depth)

        # Step 4: Add 1 for current node
        return max_child_depth + 1

• Lines 7-9: If root is None, return 0.
• Lines 12-13: If no children (leaf), depth is 1.
• Lines 16-19: Recurse on each child, track max depth.
• Line 22: Add 1 to max child depth for root.
• Time Complexity: O(n)—visit each node once.
• Space Complexity: O(h)—recursion stack (h ≤ n).

It’s like a tree-depth climber!

Alternative Solution: Iterative BFS

Why an Alternative Approach?

The iterative BFS uses a level-order traversal with a queue to compute depth in O(n) time and O(w) space (w = max width), counting levels as it goes. It’s thorough and avoids recursion, making it a good alternative for those who prefer iteration or need to track levels explicitly.

How It Works

Picture this as a tree-level counter:

• Step 1: Start queue with root, depth = 0.
• Step 2: Process each level:
• Dequeue all nodes at current level.
• Enqueue their children.
• Increment depth.
• Step 3: Return final depth.

It’s like a tree-level scanner!

Step-by-Step Example

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

• Step 1: Queue = [(1, 0)], depth = 0.
• Step 2:
• Level 0: Dequeue 1, enqueue [3, 2, 4], depth = 1.
• Level 1: Dequeue [3, 2, 4], enqueue [5, 6], depth = 2.
• Level 2: Dequeue [5, 6], no children, depth = 3.
• Result: 3.

Code for BFS Approach

from collections import deque

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

        # Step 1: Initialize queue with root and depth
        queue = deque([(root, 1)])
        max_depth = 0

        # Step 2: Process levels
        while queue:
            node, depth = queue.popleft()
            max_depth = max(max_depth, depth)
            for child in node.children:
                queue.append((child, depth + 1))

        # Step 3: Return maximum depth
        return max_depth

• Lines 7-8: Queue with (node, depth) tuples.
• Lines 11-16: BFS loop, update max depth, enqueue children.
• Line 19: Return final depth.
• Time Complexity: O(n)—visit each node once.
• Space Complexity: O(w)—queue size (w ≤ n).

It’s an iterative depth tracker!

Comparing the Two Solutions

• Recursive DFS (Best):
• Pros: O(n), O(h), simple.
• Cons: Stack space.
• Iterative BFS (Alternative):
• Pros: O(n), O(w), no recursion.
• Cons: Queue space.

Recursive DFS wins for simplicity!

Additional Examples and Edge Cases

• []: 0.
• [1]: 1.
• [1,null,2,3]: 2.

Recursive DFS handles them all!

Complexity Recap

• Recursive DFS: Time O(n), Space O(h).
• Iterative BFS: Time O(n), Space O(w).

Recursive DFS’s the elegance champ!

Key Takeaways

• Recursive DFS: Depth diving—learn at Python Basics!
• Iterative BFS: Level counting.
• Trees: N-ary is fun.
• Python: Recurse or queue, your pick!

Final Thoughts: Measure That Depth!

LeetCode 559: Maximum Depth of N-ary Tree in Python is a delightful tree challenge. Recursive DFS is your fast track, while iterative BFS offers a level-based twist. Want more? Try LeetCode 104: Maximum Depth of Binary Tree or LeetCode 617: Merge Two Binary Trees. Ready to explore? Head to Solve LeetCode 559 on LeetCode and measure that depth today!