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
Please leave a comment below if you like this post or found some errors, it will help me to improve my content.

Comments

Popular Posts from this Blog

Shell Script to find sum, product and average of given numbers - The Coding Shala

Shell Script to Create a Simple Calculator - The Coding Shala

Add two numbers in Scala - The Coding Shala

LeetCode - Number of Good Pairs Solution - The Coding Shala

Richest Customer Wealth LeetCode Solution - The Coding Shala