# Diameter of N-Ary Tree LeetCode Solution

Difficulty Level Medium
Depth First Search TreeViews 212

## Problem Statement :

The Diameter of N-Ary Tree LeetCode Solution – Given a root of an N-ary tree, you need to compute the length of the diameter of the tree.

The diameter of an N-ary tree is the length of the longest path between any two nodes in the tree. This path may or may not pass through the root.

(Nary-Tree input serialization is represented in their level order traversal, each group of children is separated by the null value.)

## Example :

### Example 1 ```Input: root = [1,null,3,2,4,null,5,6]
Output: 3
Explanation: Diameter is shown in red color.```

### Example 2 ```Input: root = [1,null,2,null,3,4,null,5,null,6]
Output: 4```

### Example 3 ```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: 7```

## Intuition :

• We are asked to calculate the diameter of an N-ary tree, which is defined as the longest path between any two nodes in the tree.
• Consider a node with n children, then there are nC2 or n Choose 2 paths passing through this node.
• The longest path will be given by maxheight1 + maxheight2 +2 where maxheight1 and maxheight2 are the two maximum heights between N children.
• Length of the longest path passing through a node = 1st Max Height among N children + 2nd Max Height among N children + 2
• With the above intuition, to find the diameter of the tree, we need to iterate over all the nodes and select the two children with the maximum height.
• To iterate over all the nodes, we can use  Depth-First Search.

## Algorithm :

• Initialize a global variable diameter, and for each node update the variable, computing the length of the longest path passing through the node.
• Define a function height(node root) {} that will return the max height.
• In the height function, Iterate over all children and pick the best two children’s height i.e. maxheight1 and maxheight2.
• Now, update the diameter global variable with the longest path passing through this node.
•  At last return maxheight1 in the height function.
• After the execution of the height function, return the diameter global variable, in the main function diameter(Node root){}.

## Code

### Diameter of N-Ary Tree Leetcode Java Solution:

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

public Node() {
children = new ArrayList<Node>();
}

public Node(int _val) {
val = _val;
children = new ArrayList<Node>();
}

public Node(int _val,ArrayList<Node> _children) {
val = _val;
children = _children;
}
};
*/

class Solution {
protected int diameter=0;
public int diameter(Node root) {
height(root);
return this.diameter;
}
// Return  the maxheight in N-arry tree
public int height(Node root){
int maxheight1=0;
int maxheight2=0;
for(Node child:root.children){
int height=height(child)+1;
if(height>maxheight1){
maxheight2=maxheight1;
maxheight1=height;
}
else if(height>maxheight2){
maxheight2=height;
}
}
this.diameter=Math.max(maxheight1+maxheight2,this.diameter);
return maxheight1;
}

}```

### Diameter of N-Ary Tree Leetcode C++ Solution:

```/*
// 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 {
int maxDiameter=0;
public:
int diameter(Node* root) {
height(root);
return this->maxDiameter;
}
int height(Node* root){
int maxheight1=0;
int maxheight2=0;
for(auto child:root->children){
int rootHeight=height(child)+1;
if(rootHeight>maxheight1){
maxheight2=maxheight1;
maxheight1=rootHeight;
}
else if(rootHeight>maxheight2){
maxheight2=rootHeight;
}
}
this->maxDiameter=max(maxheight1+maxheight2,this->maxDiameter);
return maxheight1;
}
};```

## Complexity Analysis For  Diameter of N-Ary Tree :

### Time Complexity

`O(N)`, since we are iterating each node in the tree once and only once via recursion.

`O(N)`, as recursion stack 0(N) is used.

Translate »