Suppose you work for a company, iPilgrim.com, whose n employees are organized in

Question

Suppose you work for a company, iPilgrim.com, 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 sub tree in T, as in the previous problem. Furthermore, suppose that communication in pilgrim is done the "old fashioned" way, where, for an employee, x, to send a message to an employee, y, x must route this message up to a lowest-level common supervisor of x and y, who then routes this message down to y. The problem is to design an algorithm for finding the length of a longest route that any message must travel in iPilgrim.com. That is, for any node v in T, let d_v denote the depth of v in T. The distance between two nodes v and w in T is d_v + d_w - 2d_u, where u is the LCA of v and w (as defined in the previous problem). The diameter of T is the maximum distance between two nodes in T. Thus, the length of a longest route that any message must travel in iPilgrim.com 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?

Explanation / Answer

To find the diameter of T, we will use BFS twice!

Algorithm:

Step 1: By using BFS,taking root as source, find the node with farthest distance, say point1.

Step 2: Now use Bfs again,taking point1 as source. Now the farthest distance will be the diameter of Tree.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.