Maximum Depth of N-ary Tree

Difficulty: Easy | Acceptance: 73.50% | Paid: No Topics: Tree, Depth-First Search, Breadth-First Search

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.

Nary-Tree input serialization is represented in their level order traversal, each group of children is separated by the null value (See examples).

• Examples
• Constraints
• Approach 1: Depth-First Search (Recursive)
• Approach 2: Breadth-First Search (Iterative)

Examples

Example 1:

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

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]
Output: 5

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.
0 <= Node.val <= 10⁴.

Depth-First Search (Recursive)

Intuition We can recursively calculate the depth of each child subtree. The depth of the current node is the maximum depth among its children plus one (for the current node itself).

Steps

• If the root is null, return 0.
• Initialize a variable max_depth to 0.
• Iterate through all children of the root.
• For each child, recursively call maxDepth and update max_depth with the maximum value returned.
• Return max_depth + 1.

Complexity

• Time: O(N), where N is the number of nodes in the tree. We visit each node exactly once.
• Space: O(H), where H is the height of the tree. This represents the maximum depth of the recursion stack. In the worst case (skewed tree), H = N.
• Notes: This is the most intuitive approach for tree depth problems.

Breadth-First Search (Iterative)

Intuition We can perform a level-order traversal (BFS) using a queue. We count how many levels we traverse to determine the depth.

Steps

• If the root is null, return 0.
• Initialize a queue and add the root to it.
• Initialize depth to 0.
• While the queue is not empty:
  • Increment depth.
  • Get the size of the current level (number of nodes at the current depth).
  • Iterate size times:
    • Dequeue a node.
    • Enqueue all of its children.
• Return depth.

Complexity

• Time: O(N), where N is the number of nodes. We process each node exactly once.
• Space: O(W), where W is the maximum width of the tree (maximum number of nodes at any level). In the worst case, this could be close to N.
• Notes: Useful if you need to process nodes level by level, though slightly more verbose than DFS for just finding depth.