# Maximum Depth of N-ary Tree
**Difficulty:** EASY
[External](https://leetcode.com/problems/maximum-depth-of-n-ary-tree)
Canonical: https://scaleengineer.com/dsa/problems/maximum-depth-of-n-ary-tree
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**Data structures:** Tree
**Companies:** [Datadog](https://scaleengineer.com/companies/datadog)
---
## Problem
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)._

**Example 1:**

![](https://assets.glich.co/dsa/maximum-depth-of-n-ary-tree/image0.png)

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

**Example 2:**

![](https://assets.glich.co/dsa/maximum-depth-of-n-ary-tree/image1.png)

**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, 104]`.
* The depth of the n-ary tree is less than or equal to `1000`.

# Approaches
## Iterative Breadth-First Search (BFS)
This approach finds the maximum depth by traversing the tree level by level. It uses a queue to manage the nodes at each level and counts the number of levels traversed, which corresponds to the depth of the tree.
**Time:** O(N), where N is the total number of nodes. Each node is enqueued and dequeued exactly once. · **Space:** O(W), where W is the maximum width of the tree. The space is used by the queue, which holds at most all nodes at the widest level. In the worst case (a complete, wide tree), the width W can be close to N.
**Pros:** Avoids recursion, preventing potential `StackOverflowError` for extremely deep trees.; Can be more space-efficient than DFS for very deep and narrow trees.
**Cons:** Can be less space-efficient than DFS for wide and shallow trees. For the given constraints, its worst-case space complexity (O(N)) is higher than DFS's (O(H)).; The implementation is slightly more verbose than the recursive solution.
### Explanation
The algorithm works by performing a level-order traversal.
*   We start with a queue containing just the root node and initialize the depth to 0.
*   We then enter a loop that continues as long as there are nodes to process in the queue.
*   In each iteration of the loop, we process one full level of the tree. We first record the number of nodes currently in the queue (`levelSize`). These are all the nodes at the current depth.
*   We increment our `depth` counter because we are moving one level deeper.
*   We then dequeue `levelSize` nodes, and for each node, we enqueue all of its children. This prepares the queue with all nodes for the next level.
*   Once the queue is empty, it means we have visited all nodes, and the `depth` counter holds the maximum depth of the tree.
```java
/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
};
*/
import java.util.LinkedList;
import java.util.Queue;
import java.util.List;

class Solution {
    public int maxDepth(Node root) {
        if (root == null) {
            return 0;
        }
        
        Queue<Node> queue = new LinkedList<>();
        queue.offer(root);
        
        int depth = 0;
        
        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            depth++;
            for (int i = 0; i < levelSize; i++) {
                Node currentNode = queue.poll();
                if (currentNode.children != null) {
                    for (Node child : currentNode.children) {
                        queue.offer(child);
                    }
                }
            }
        }
        
        return depth;
    }
}
```
### Algorithm
- If the `root` is `null`, return 0.
- Initialize a `Queue` and add the `root` node.
- Initialize `depth` to 0.
- While the queue is not empty:
  - Get the number of nodes at the current level, `levelSize`.
  - Increment `depth`.
  - Loop `levelSize` times:
    - Dequeue a node.
    - Enqueue all of its children.
- Return `depth`.

## Recursive Depth-First Search (DFS)
This approach leverages the recursive nature of a tree's depth. The depth of a tree is 1 (for the root) plus the maximum depth of any of its subtrees. This is solved elegantly using a recursive function that traverses the tree in a depth-first manner.
**Time:** O(N), where N is the total number of nodes in the tree. We visit each node exactly once during the traversal. · **Space:** O(H), where H is the height of the tree. This space is consumed by the recursion call stack. In the worst case of a skewed tree, H can be equal to N. However, given the problem constraint that the depth is at most 1000, the worst-case space is manageable.
**Pros:** Very intuitive and aligns with the mathematical definition of tree depth.; The code is clean, concise, and easy to understand.; Given the problem constraints (depth <= 1000), it is more space-efficient in the worst case than the BFS approach.
**Cons:** For extremely deep trees not bound by the problem's constraints, it could lead to a `StackOverflowError`.
### Explanation
The core idea is to define the depth of a tree in terms of the depths of its subtrees.
*   The base case for the recursion is a `null` node, which has a depth of 0.
*   For a non-null node, we need to find the maximum depth among all its children. We initialize a variable, `maxChildDepth`, to 0.
*   We then iterate through each child of the current node and make a recursive call to `maxDepth` on that child.
*   We keep track of the maximum depth returned by these recursive calls in `maxChildDepth`.
*   Finally, the depth of the tree rooted at the current node is `1` (for the node itself) plus the `maxChildDepth`. This value is returned.
```java
/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
};
*/
import java.util.List;

class Solution {
    public int maxDepth(Node root) {
        if (root == null) {
            return 0;
        }
        
        int maxChildDepth = 0;
        if (root.children != null) {
            for (Node child : root.children) {
                maxChildDepth = Math.max(maxChildDepth, maxDepth(child));
            }
        }
        
        return 1 + maxChildDepth;
    }
}
```
### Algorithm
- If the `root` is `null`, return 0 (base case).
- Initialize `maxChildDepth` to 0.
- For each `child` of the `root`:
  - Recursively call `maxDepth(child)` and update `maxChildDepth` with the maximum value found so far.
- Return `1 + maxChildDepth`.

# Solutions
### Java

```java
/* // Definition for a Node. class Node { public int val; public List<Node> children; public Node() {} public Node(int _val) { val = _val; } public Node(int _val, List<Node> _children) { val = _val; children = _children; } }; */ class Solution { public int maxDepth ( Node root ) { if ( root == null ) { return 0 ; } int ans = 1 ; for ( Node child : root . children ) { ans = Math . max ( ans , 1 + maxDepth ( child )); } return ans ; } }
```

### CPP

```cpp
/* // Definition for a Node. class Node { public: int val; vector<Node*> children; Node() {} Node(int _val) { val = _val; } Node(int _val, vector<Node*> _children) { val = _val; children = _children; } }; */ class Solution { public: int maxDepth ( Node * root ) { if ( ! root ) return 0 ; int ans = 1 ; for ( auto & child : root -> children ) ans = max ( ans , 1 + maxDepth ( child )); return ans ; } };
```

### Python

```python
""" # Definition for a Node. class Node: def __init__(self, val=None, children=None): self.val = val self.children = children """ class Solution : def maxDepth ( self , root : 'Node' ) -> int : if root is None : return 0 return 1 + max ([ self . maxDepth ( child ) for child in root . children ], default = 0 )
```