Question

The time delay of a long-distance call can be determined by multiplying a small fixed constant by the number of communication links on the telephone network between the caller and callee. Suppose the telephone network of a company named RT&T is a free tree. The engineers of RT&T want to compute the maximum possible time delay that may be experienced in a long-distance call. Given a free tree T, the diameter of T is the length of a longest path between two nodes of T. Give an efficient algorithm for computing the diameter of T.

Answer 1

Answer:

We can compute the diameter of the tree T by a pruning procedure, starting at the leaves (external nodes).

• Remove all leaves of T. Let the remaining tree be T1.
• Remove all leaves of T1. Let the remaining tree be T2.
• Repeat the "remove" operation as follows: Remove all leaves of Ti. Let remaining tree be Ti+1.
• When the remaining tree has only one node or two nodes, stop! Suppose now the remaining tree is Tk.
• If Tk has only one node, that is the center of T. The diameter of T is 2k.
• If Tk has two nodes, either can be the center of T. The diameter of T is 2k+1.

Explanation:

We can compute the diameter of the tree T by a pruning procedure, starting at the leaves (external nodes).

• Remove all leaves of T. Let the remaining tree be T1.
• Remove all leaves of T1. Let the remaining tree be T2.
• Repeat the "remove" operation as follows: Remove all leaves of Ti. Let remaining tree be Ti+1.
• When the remaining tree has only one node or two nodes, stop! Suppose now the remaining tree is Tk.
• If Tk has only one node, that is the center of T. The diameter of T is 2k.
• If Tk has two nodes, either can be the center of T. The diameter of T is 2k+1.