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

$\text{Option A: True}$ 

Distance is strictly reducing at each step.

 

$\text{Option B: True}$ 

Distance increasing initially from $U_1$ to $U_2$ to $U_3$ and decreasing from $U_3$ to $U_4$

 

$\text{Option D: True}$ 

Distance decreased and then remained constant.

 

$\text{Option E: True}$  

Thus for same tree, distance between last two vertices is different based on $U_1$. It is $4$ in first case and $3$ in second case.

 

$\text{Option C: False}$  

See the example for option $(A).$ The path connecting $U_2$ to $U_3$ is of length $4$. But it is not the longest path. The longest path is the one connecting $U_1$ and $U_2$ i.e., of length $5.$

 

 

Comments

Let u3 be the leaf that is farthest from u2

You have violated this rule in the counter example of Option A. u1 is farthest away from u3 in your example.

---

I did it in mind. Wowowowowowowowoow

---

This is the wrong interpretation of the question, It is asking which of them is correct all the time

Answer 2

Answer is $C$

This post explains it nicely:

https://www.quora.com/How-does-following-algorithm-for-finding-longest-path-in-tree-work

Comments

Could  u plz explain why other options are wrong I m not able to visualize

Answer 3

answer is c. as it seems to be.

and actually thats the standard method of calculating the longest distance in a tree.

Answer 4

The problem is based on diameter of the tree, the diameter of the tree is is defined as a longest path or route between any two nodes in a tree. So there may be many pairs( u , v ) which have length equals to the diameter of the tree , once you find any node which is one end of the diameter then the node which present at maximum distance to it is another end of the diameter , and if you calculating this again and again , till you encounter the visited leaf again , then each and every time , you will go to new end of the diameter and each time you get the same distance. It means if you start with any leaf node u1 then it is not necessary that this node is one end of the diameter, now u2 is the node which is at maximum distance to it.. then definitely u2 node is one end of the diameter and u3 is maximum distance node to it (u2 - u3 ) is the diameter. and now if you proceed further, you will get the the same distance again and again till the last node....

So for some tree  it will give  x , y , y , y , y , y ..... where

x < y ( means initial starting node is not the end of diameter )

Otherwise  it will  give  y , y , y , y , y...  ( y = diameter ).

Option C is the correct answer.

Comments

IN THINK AFTER WE REACH ONE END OF DIAMETER WE WILL KEEP OSCILLATING LIKE X,Y,X,Y,X,Y AND SO ON.................