Suppose you work for a company whose n employees are organiz

Suppose you work for a company whose n employees are organized in a tree T, so that each node is associated with an employee and each employee is considered a supervisor for all the employees(including themselves) in his or her subtree in T. Suppose communication in compnay is done the old fashioned way where for an employee x to send a message to any employee ym x must route this message up to the lowest level common supervisor the length of a longest route that any message must travein in compnay. That is, for any node v in T let dv denote the depth of v in T. The distance between two nodes v and w is T is dv+dw-2du, where u is the LCA of v and w. The diameter of T is the maximum distance between two nodes in T. Thus, the length of the longest route that any message must travel in company is equal to the diameter of T. Describe an efficient algorithm for finding the diameter of T. What is the running time of your method?

Solution

Before understanding the solution for n-ary tree, we need to understand the Diameter calculation for binary tree. The diameter of a binary tree will be the maximum value from the given 3 values

1. Diameter of the left subtree
2. Diameter of the right subtree
3. Height of the left subtree + Height of right subtree + 2

If either 1 or 2 is the maximum, means the longest path for diameter doesn\'t go through the root node. If 3 is the largest value, means the longest path for diameter goes through the root node and one of the two end nodes of the path is in left subtree and other one is in right subtree.

So for solving the problem for binary tree we need to find all these three values for each node in bottom up way. Now we can extend this idea for the n-ary tree.

For binary tree we have at max 2 child. So we calculated the diameter of its left subtree and right subtree and then looked for max of these values.(Yes we also compared the value from point 3 in the max calculation but as the first step we had to compare the first 2 values only.) Now in n-ary tree as we have at max n child nodes so we have to calculate the Diameter of each subtree rooted by the n child nodes, then get the max value out of these n diameters. Suppose this value is maxChildDiameter. Now we need to calculate the value of diameter through the current node.(this is corresponding to the 3rd value for binary tree) For calculating it we need to calculate the 2 nodes which are at maximum distance from the current node and these 2 should be in different child subtrees. For finding them we need to iterate over all the child nodes and for each of them we need to find the maximum distant node and need to calculate the maximum distance. After completion of iteration over all child nodes we need to find max value out of them and second max value. We will add these 2 values + the distances to their corresponding root node to our current node. This value will become the Diameter through the current Node. Now we need to compare this value with the maxChildDiameter value. The greater of these two values will become the Diameter of subtree rooted at the current Node.

This calculation will be done recursively at each node and the Diameter value calculated at root node will return the diameter of the n-ary tree.

The run time complexity would be O(n) as we travers the tree only once.