### 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<Node> queue = new LinkedList<Node>(); 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**

- Height of a Binary Tree
- Find Minimum Depth of Binary Tree
- Count Unique Binary Trees
- Connect nodes at the same level in a binary tree
- How to invert a Binary tree

## Comments

## Post a Comment