> For the complete documentation index, see [llms.txt](https://yyloumike.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://yyloumike.gitbook.io/leetcode/tree/n-ary-tree-traversal-3-qs/0559.-maximum-depth.md).

# 0559. Maximum Depth

Easy  |  Tree + Level-order Traversal  |  40 ms (93.70%),  16 MB (46.68%)

{% tabs %}
{% tab title="❓ Problem Statement" %}

> Source: [LeetCode - Maximum Depth of N-ary Tree](https://leetcode.com/problems/maximum-depth-of-n-ary-tree/)\
> GitHub: [Solution / Performance](https://github.com/yylou/leetcode/tree/main/0559-maximum-depth-of-n-ary-tree)

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).*
{% endtab %}

{% tab title="✍🏻 Constraints & Example" %}
**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`.
  {% endtab %}
  {% endtabs %}

{% tabs %}
{% tab title=" 💡 Ideas" %}
{% hint style="info" %}
Extension question of **Level-order traversal**.
{% endhint %}

While traversing the tree in level order, we need to **record the current level (depth)**.
{% endtab %}
{% endtabs %}

{% tabs %}
{% tab title=" 🤖 Python3" %}

```python
class Solution:
    def maxDepth(self, root: 'Node') -> int:
        # (base case)
        if not root: return 0
        if not root.children: return 1
        
        # ==================================================
        #  N-ary Tree + Level Order Traversal              =
        # ==================================================
        # time  : O(n)
        # space : O(n)
        
        maxDepth = 0
        stack = [root]
        
        while stack:
            for i in range(len(stack)):
                node = stack.pop(0)
                
                for element in node.children:
                    stack.append(element)
            
            maxDepth += 1
            
        return maxDepth
```

{% endtab %}

{% tab title="🤖 Java" %}

```java
class Solution {
    /**
     * @time  : O(n)
     * @space : O(n)
     */
    
    public int maxDepth(Node root) {
        /* base case */
        if(root == null) return 0;
        if(root.children == null) return 1;
        
        int maxDepth = 0;
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        
        while(!queue.isEmpty()) {
            int size = queue.size();
            for(int i=0 ; i<size ; i++) {
                Node node = queue.remove();
                
                if(node.children != null) {
                    for(Node element: node.children) queue.add(element);
                }
            }
            
            maxDepth++;
        }
        
        return maxDepth;
    }
}
```

{% endtab %}
{% endtabs %}