TIFR CSE 2012 | Part B | Question: 15

Question

Let $T$ be a tree of $n$ nodes. Consider the following algorithm, that constructs a sequence of leaves $u_{1}, u_{2}...$. Let $u_{1}$ be some leaf of tree. Let $u_{2}$be a leaf that is farthest from $u_{1}$. Let $u_{3}$ be the leaf that is farthest from $u_{2}$, and, in general, let $u_{i+1}$ be a leaf of $T$ that is farthest from $u_{i}$ (if there are many choices for $u_{i+1}$, pick one arbitrarily). The algorithm stops when some $u_{i}$ is visited again. What can u say about the distance between $u_{i}$ and $u_{i+1}$, as $i = 1, 2,...?$

• A. For some trees, the distance strictly reduces in each step.
• B. For some trees, the distance increases initially and then decreases.
• C. For all trees, the path connecting $u_{2}$ and $u_{3}$ is a longest path in the tree.
• D. For some trees, the distance reduces initially, but then stays constant.
• E. For the same tree, the distance between the last two vertices visited can be different, based on the choice of the first leaf $u_{1}$.

Comments

based on this concept ask in gate 2019

https://gateoverflow.in/302802/gate2019-46

---

Then according to this answer, all should be correct right

---

Why can’t all be the answers like in an MSQ

Answer 1

Hi Guys,

If question asks which of the following option is false then option  (C) is false rest all are true. Following is my explanation (with the help of examples) for the different parts of this question.

Comments

For first option, So, if we consider inter-nodal distances to be 1, u1 to u2 distance is 5, hence farthest, u2 to u3 again 5, but u3 to u4 is 3 whereas I4 is at distance 4, so u4 should have been I4, isn't it?

---

In your examples the node which is farthest from u2 is u3, but that is wrong as there is u1 which is already farthest from u2. If there is a u3 then the distance between u1-u2 and u2-u3 would be the same.

---

Let u3 be the leaf that is farthest from u2

You have violated this rule in the counter example of Option C.

Answer 2

The distance remains constant, it can never increase or decrease, as in the algorithm it is said that u1 is at farthest distance from u2 and if there is no such u3, then there is no other vertex which is farthest from u1, and we reach back to u1, the algorithm stops. If there is a u3 then u2-u3 will be a longest path in the tree.

option C.

Answer 3

Correct option is (C) The path connecting U2 and U3 is a longest path in the tree.

Because, problem is based on diameter of the tree, the diameter of the tree is defined as a longest path or route between any two nodes in a tree and question itself says that leaf ui is farthest from leaf ui+1. 

Question also gives the stopping condition of algorithm that "The algorithm stops when some ui is visited again."

Once diameter is found, if we try to find diameter again and again we can visit the same ui again hence the stopping condition of algo.

 

Answer 4

Answer should be option C as distance between starting leaf and the last leaf will always be the largest path.