### Maximum Depth of N-ary Tree - The Coding Shala

Last Updated: 26-Jan-2021
Home >> Interview Questions >> Maximum Depth of N-ary Tree

In this post, we will learn how to find the Maximum Depth of the N-ary Tree using recursion and level-order traversal.

## Maximum Depth of N-ary Tree

Given an 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.

For example, given a 3-ary tree:

1
/  |  \
3  2  4
/ \
5   6
We should return its max depth, which is 3.

## Maximum Depth of N-ary Tree Java Program

Approach 1

We can do a level-order traversal of the N-ary tree and return the maximum level.

Java Program:

```/*
// Definition for a Node.
class Node {
public int val;
public List<Node> children;

public Node() {}

public Node(int _val,List<Node> _children) {
val = _val;
children = _children;
}
};
*/
class Solution {
public int maxDepth(Node root) {
int level = 0;
if(root == null) return level;
queue.offer(root);
while(!queue.isEmpty()){
int size = queue.size();
for(int i=0; i<size; i++){
Node tmp = queue.poll();
for(int j=0;j<tmp.children.size();j++) queue.offer(tmp.children.get(j));
}
level++;
}
return level;
}
}
```

Approach 2

Using recursion.

Java Program:

```/*
// Definition for a Node.
class Node {
public int val;
public List<Node> children;

public Node() {}

public Node(int _val,List<Node> _children) {
val = _val;
children = _children;
}
};
*/
class Solution {
public int maxDepth(Node root) {
if(root == null) return 0;
int level = 0;
for(int i = 0; i<root.children.size(); i++){
int l_tmp = maxDepth(root.children.get(i));
if(l_tmp>level) level = l_tmp;
}
return level+1;
}
}
```

Other Posts You May Like