Diameter of N-Ary Tree

Jyothi
1 min readMar 28, 2022

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.

Initially by seeing the problem its like what is diameter and that too in N-ary tree.

But if see normally, it is sum of longest depths or heights .

We can go with the post-order/DFS approach. We will be calculating the diameter after going over the children. Its a simple solution, but a tricky.

Below is my solution:

void get_max_level(struct Node * nd, int *lvl, int *max_d){
int curlvl = *lvl;
int ii, m1 = 0, m2 =0;
if (!nd)
return;
(*lvl)++;
/* return if no children */
if (!(nd->numChildren))
return;
int clvl;
/* get each child height */
for (ii=0; ii<nd->numChildren; ii++){
clvl = 0;
get_max_level(nd->children[ii], &clvl, max_d);
/* save max 2 height values */
if (m1 < clvl){
m2 = m1;
m1 = clvl;
}
else if (m2 < clvl)
m2 = clvl;
}
if ((*max_d) < (m2+m1))
*max_d = (m2+m1);

(*lvl) += m1;
return;
}
int* diameter(struct Node* root) {
int lvl = 0, maxd = 0;
get_max_level(root, &lvl, &maxd);
if (maxd < lvl) return lvl-1;
return maxd;
}

Please give your comments.

--

--