IAE Academy

GATE 2025 CS2 Q.59: solution and answer

GATE 2025 · CS2Q.59 · 2 marks · NAT

Consider the following algorithm someAlgo that takes an undirected graph G as input.

someAlgo(G)
  1. Let v be any vertex in G. Run BFS on G starting at v. Let u be a vertex in G at maximum distance from v as given by the BFS.
  2. Run BFS on G again with u as the starting vertex. Let z be the vertex at maximum distance from u as given by the BFS.
  3. Output the distance between u and z in G.

The output of someAlgo() for the tree shown in the given figure is ___________. (Answer in integer)

GATE 2025 CS2 question 59: An unrooted tree with 14 vertices and 13 edges.Tap to open full size
Figure from the GATE 2025 CS2 paper. It is part of the question.
Figure description

An unrooted tree with 14 vertices and 13 edges. Two internal hub vertices P and Q (each degree 4) are joined directly by one edge. P also connects to: a leaf L1; a degree-3 vertex M, which itself connects to two further leaves T1 and R1; and a path P-L2-L3 (L2 degree 2) ending in leaf L3. Q also connects to: two leaves B1 and B2; and a path Q-R2-R3-R4 where R2 is degree 3 (also branching to leaf T2) and R3 is degree 2, ending in leaf R4. No vertex labels are printed in the figure; positions only show dots and connecting line segments.

Answer and solution

ANSWER

someAlgo(T) outputs 6.

Official answer: 6Source: Official answer key, GATE 2025 CS2 (IIT Roorkee)

  1. someAlgo is the classical double-BFS algorithm for a tree's diameter: BFS from any vertex v finds a vertex u that is a guaranteed endpoint of some longest path (diameter path) in the tree; BFS from u then finds the true farthest vertex z, and the reported distance u-z equals the diameter of T. This is a proven property specific to trees.

  2. Read the tree T from the figure: two degree-4 hub vertices P and Q are joined by a single edge. P also connects to a leaf L1, to a degree-3 vertex M that itself branches to two leaves T1 and R1, and to a 2-edge chain P-L2-L3 ending in leaf L3. Q also connects to two leaves B1 and B2, and to a chain Q-R2-R3-R4 where R2 additionally branches to a leaf T2 and R3 is degree 2.

  3. Because the whole tree hangs off the single bridge edge P-Q, the diameter equals (farthest reach from P, not through Q) + 1 (the P-Q edge) + (farthest reach from Q, not through P).

  4. Farthest reach from P away from Q: L1 is at distance 1; the M-branch reaches T1 or R1 at distance 2 (P-M-T1); the L2 chain reaches L3 at distance 2 (P-L2-L3). The maximum is 2.

  5. Farthest reach from Q away from P: B1 and B2 are at distance 1; the R2 branch reaches T2 at distance 2 (Q-R2-T2); the chain Q-R2-R3-R4 reaches R4 at distance 3. The maximum is 3.

  6. Diameter = 2 (P side) + 1 (P-Q edge) + 3 (Q side) = 6, realized for example by the path T1-M-P-Q-R2-R3-R4 (6 edges).

  7. Since double-BFS is guaranteed to output the diameter of a tree, someAlgo(T) outputs 6.

KEY IDEA

The double-BFS algorithm (BFS from an arbitrary vertex to find one diameter endpoint, then BFS from that endpoint to find the other) correctly computes the diameter of a tree — a classical, provable result that fails for general graphs but is guaranteed for trees.

WATCH OUT FOR

Treating the two hub vertices' branch depths asymmetrically or forgetting to add the connecting P-Q edge itself (giving 5 instead of 6), or missing the T2 branch off R2 and wrongly taking the Q-side depth as only 2 (via B1/B2) instead of 3 (via R2-R3-R4).

From the GATE 2025 CS2 paper. Every question of this paper · Download the full paper · All 28 Graph algorithms questions, with notes

More Graph algorithms questions