Domain 1EasyCORE

Maximum Depth of N-ary Tree

The problem asks us to find the maximum depth of an N-ary tree. The maximum depth is defined as the number of nodes along the longest path from the root node down to the farthest leaf node. An N-ary tree is a tree where each node can have up to N children.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Tree#Depth-first Search#Breadth-first Search

559. Maximum Depth of N-ary Tree

Model: qwen2.5-coder:14b
Topics: Tree,Depth-first Search,Breadth-first Search
FAANG asked: 1
Acceptance rate: 69.6%


Problem Breakdown

The problem asks us to find the maximum depth of an N-ary tree. The maximum depth is defined as the number of nodes along the longest path from the root node down to the farthest leaf node. An N-ary tree is a tree where each node can have up to N children.

Inputs:

  • A root node of an N-ary tree.

Outputs:

  • An integer representing the maximum depth of the tree.

Implicit Constraints or Tricky Edge Cases:

  • The tree could be empty (root is null), in which case the depth should be 0.
  • Each node can have zero or more children, so we need to handle cases where a node has no children (leaf nodes).

Intuition

A brute-force approach would involve traversing all paths from the root to the leaf nodes and keeping track of the maximum path length. However, this approach is inefficient in terms of both time and space complexity because it requires visiting every node multiple times.

The key insight is to use a recursive or iterative depth-first search (DFS) or breadth-first search (BFS) to traverse the tree while keeping track of the current depth. This way, we can efficiently compute the maximum depth by exploring each path only once.

Approach

We will use a recursive DFS approach to solve this problem. The idea is to recursively calculate the depth of each subtree and then determine the maximum depth among all subtrees. Here are the steps:

  1. If the root is null, return 0 because an empty tree has a depth of 0.
  2. Initialize a variable max_depth to 0.
  3. For each child of the current node, recursively calculate its depth and update max_depth if the calculated depth is greater than the current max_depth.
  4. Return max_depth + 1 to account for the current node.

Complexity Analysis

  • Time Complexity: O(n), where n is the number of nodes in the tree. We visit each node exactly once.
  • Space Complexity: O(h), where h is the height of the tree. This is due to the recursion stack. In the worst case, when the tree is a linked list (completely unbalanced), the space complexity is O(n).

Solution

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

def maxDepth(root: 'Node') -> int:
    if root is None:
        return 0
    
    max_depth = 0
    for child in root.children:
        max_depth = max(max_depth, maxDepth(child))
    
    return max_depth + 1

Edge Cases Handled

  • Empty Tree: If the input tree is empty (root is null), the function returns 0.
  • Single Node Tree: If the tree consists of only one node (no children), the function correctly returns a depth of 1.
  • Balanced and Unbalanced Trees: The solution handles both balanced and unbalanced trees efficiently.