# Algorithm to find diameter of a tree using BFS/DFS. Why does it work?

This link provides an algorithm for finding the diameter of an undirected tree using BFS/DFS. Summarizing:

Run BFS on any node s in the graph, remembering the node u discovered last. Run BFS from u remembering the node v discovered last. d(u,v) is the diameter of the tree.

Why does it work ?

Page 2 of this provides a reasoning, but it is confusing. I am quoting the initial portion of the proof:

Run BFS on any node s in the graph, remembering the node u discovered last. Run BFS from u remembering the node v discovered last. d(u,v) is the diameter of the tree.

Correctness: Let a and b be any two nodes such that d(a,b) is the diameter of the tree. There is a unique path from a to b. Let t be the first node on that path discovered by BFS. If the paths $$p_1$$ from s to u and $$p_2$$ from a to b do not share edges, then the path from t to u includes s. So

$$d(t,u) \ge d(s,u)$$

$$d(t,u) \ge d(s,a)$$

The inequalities do not make sense to me.

• I don't find the quote in the linked question.
– Raphael
Mar 20, 2014 at 13:30
• Try replacing "do not share edges" with "do not share vertices" in the solution. Mar 20, 2014 at 13:42
• You are using only BFS, not DFS. May 24, 2017 at 11:14
• i'm pretty sure the same method works with two DFSs, and instead of choosing $u$ to be the vertex discovered last, choose $u$ to be a vertex with maximal depth in the depth-first tree. Dec 29, 2020 at 19:40

The intuition behind is very easy to understand. Suppose I have to find longest path that exists between any two nodes in the given tree.

After drawing some diagrams we can observe that the longest path will always occur between two leaf nodes( nodes having only one edge linked). This can also be proved by contradiction that if longest path is between two nodes and either or both of two nodes is not a leaf node then we can extend the path to get a longer path.

So one way is to first check what nodes are leaf nodes, then start BFS from one of the leaf node to get the node farthest from it.

Instead of first finding which nodes are leaf nodes , we start BFS from a random node and then see which node is farthest from it. Let the node farthest be x. It is clear that x is a leaf node. Now if we start BFS from x and check farthest node from it, we will get our answer.

But what is the guarantee that x will be a end point of a maximum path?

Let's see by an example :-

       1
/ /\ \
6 2  4 8
\ \
5 9
\
7


Suppose I started my BFS from 6. The node at maximum distance from 6 is node 7. Using BFS we can get this node. Now we star BFS from node 7 to get node 9 at maximum distance. Path from node 7 to node 9 is clearly the longest path.

What if BFS that started from node 6 gave 2 as the node at maximum distance. Then when we will BFS from 2 we will get 7 as node at maximum distance and longest path will be then 2->1->4->5->7 with length 4. But the actual longest path length is 5. This cannot happen because BFS from node 6 will never give node 2 as node at maximum distance.

Hope that helps.

• thats a simple & clear explanation! thanks :) Aug 10, 2018 at 4:46
• this does not answer why the procedure will work in general. Jul 7 at 5:48

All parts of proving the claim hinge on 2 crucial properties of trees with undirected edges:

• 1-connectedness (ie. between any 2 nodes in a tree there is exactly one path)
• any node can serve as the root of the tree.

Choose an arbitrary tree node $s$. Assume $u, v \in V(G)$ are nodes with $d(u,v) = diam(G)$. Assume further that the algorithm finds a node $x$ starting at $s$ first, some node $y$ starting at $x$ next. wlog $d(s,u) \geq d(s,v)$. note that $d(s,x) \geq d(s,y)$ must hold, unless the algorithm's first stage wouldn't end up at $x$. We will see that $d(x,y) = d(u,v)$.

The most general configuration of all nodes involved can be seen in the following pseudo-graphics ( possibly $s = z_{uv}$ or $s = z_{xy}$ or both ):

(u)                                            (x)
\                                            /
\                                          /
\                                        /
( z_uv )---------( s )----------( z_xy )
/                                        \
/                                          \
/                                            \
(v)                                            (y)


we know that:

1. $d(z_{uv},y) \leq d(z_{uv},v)$. otherwise $d(u,v) < diam(G)$ contradicting the assumption.
2. $d(z_{uv},x) \leq d(z_{uv},u)$. otherwise $d(u,v) < diam(G)$ contradicting the assumption.
3. $d(s,z_{xy}) + d(z_{xy},x) \geq d(s,z_{uv}) + d(z_{uv},u)$, otherwise stage 1 of the algorithm wouldn't have stopped at $x$.
4. $d(z_{xy},y) \geq d(v,z_{uv}) + d(z_{uv},z_{xy})$, otherwise stage 2 of the algorithm wouldn't have stopped at $y$.

1) and 2) imply $\, \\ d(u,v) = d(z_{uv},v) + d(z_{uv},u) \\ \qquad\geq d(z_{uv},x) + d(z_{uv},y) = d(x,y) + 2\, d(z_{uv}, z_{xy}) \\ \qquad\qquad\geq d(x,y)$.

3) and 4) imply $\, \\ d(z_{xy},y) + d(s,z_{xy}) + d(z_{xy},x) \\ \qquad\geq d(s,z_{uv}) + d(z_{uv},u) + d(v,z_{uv}) + d(z_{uv},z_{xy}) \qquad\qquad\qquad\qquad \\ \,$ equivalent to $\, \\ d(x,y) = d(z_{xy},y) + d(z_{xy},x) \\ \qquad\geq 2*\,d(s,z_{uv}) + d(v,z_{uv}) + d(u,z_{uv}) \\ \qquad\qquad\geq d(u,v)$.

therefore $d(u,v) = d(x,y)$.

analogue proofs hold for the alternative configurations

                 (u)                          (x)
\                          /
\                        /
\                      /
( s )---------( z_uv )----------( z_xy )
/                      \
/                        \
/                          \
(v)                          (y)


and

                          (x)        (u)
/            \
/              \
/                \
( s )---------( z_xy )----------( z_uv )
\                /
\              /
\            /
(y)        (v)


these are all possible configurations. in particular, $x \not\in path(s,u), x \not\in path(s,v)$ due to the result of stage 1 of the algorithm and $y \not\in path(x,u), y \not\in path(x,v)$ due to stage 2.

• (1) Regarding the first graphic, shouldn't the path from s to x always contain vertices u and v in some order since they are present on tree generated by BFS? (2) Could you clarify how the inequalities are obtained ? (3) Since the BFS starting from s and that starting from x contain u,v somewhere on the path, I believe the graphic should be as shown in the link imgur.com/jQ94erY . How does the reasoning you provided apply here ? Mar 21, 2014 at 5:39
• @curryage note that the tree is given and not being constructed by the bfs! specific answers: ad 1) no. imagine a refinement of the tree in graphics (1) by adding arbitrarily many nodes on the edge $(s, z_{xy})$ and exactly 1 node on the edge $(z_{xy}, x)$. the first stage bfs will then end at x. ad 2) which inequality/ies are unclear? we are always assuming that $(u,v)$ be a path the length of the graph's diameter $diag(G)$. this is well defined as G is 1-connected. ad 3) no: 3.1 there is more than 1 path between any 2 nodes apart from $(s,y)$, so the graph is not a tree. ... Mar 21, 2014 at 15:27
• @curryage ... 3.2 $d(x,y) > d(u,v)$; this is impossible as $d(u,v) = diam(G)$ by assumption and a graph's diameter is the maximal minimum distance between any two nodes. in the case of a tree there is exactly 1 path between any 2 nodes, so the definition reduces to 'maximum distance between any two nodes'. Mar 21, 2014 at 15:31
• I don't see how the statement after "equivalent to" is equivalent to the preceding statement (after "3) and 4) imply") -- where did the $d(s, z_{xy})$ term on the LHS go? Dec 23, 2020 at 0:06

There's an error in the linked solution set (see update 2 below), but it can be easily corrected with @Yuval Filmus's suggestion in the question's comment, which further allows us to rule out one of the possibilities mentioned in the solution set.

Let $$s$$ be the root of the first BFS and let $$u$$ be the final vertex discovered. Also, let $$d(a,b)$$ be a diameter. Clearly, $$a$$, $$b$$, and $$u$$ must all be leaves, since otherwise $$d(a,b)$$ wouldn't be a diameter, and $$u$$ wouldn't be discovered last. Let $$t$$ be the lowest common ancestor of $$a$$ and $$b$$.

We claim that $$t$$ must be an ancestor of $$u$$. Suppose that it were not, then let $$r$$ be lowest common ancestor of $$u$$ and $$t$$. Then since $$u$$ was discovered last, we have $$d(u,s) \geq d(u,r) \geq d(a,r) > d(a,t)$$ since $$r \neq t$$, and thus $$d(u,b) = d(u,r) + d(r,t) + d(t,b) > d(a,t) + d(t,b) = d(a,b)$$, contradicting the latter being a diameter.

Hence $$t$$ is an ancestor of $$u$$, and then $$d(t,u) \geq d(t,a)$$, since otherwise $$u$$ would not have been discovered last. Also, $$d(t,u) \leq d(t,a)$$, since otherwise $$d(a,b)$$ would not have been a diameter. Hence $$d(u,b) = d(a,b)$$ and thus $$u$$ is the endpoint of some diameter, and thus the second BFS works.

Update 2

Note that the linked solution set contains an error:

If the paths $$p_1$$ from $$s$$ to $$u$$ and $$p_2$$ from $$a$$ to $$b$$ do not share edges, then the path from $$t$$ to $$u$$ includes $$s$$.

Consider the following counterexample: suppose $$s$$ is the root of the first BFS tree, and $$t$$ is the lowest common ancestor of leaves $$a$$, $$u$$, and $$b$$. No edges are shared; only the vertex $$t$$ is shared. Let $$d(a,t) = d(b,t) = d(u,t) = 2$$, and let $$d(s,t)=1$$. Finally, suppose $$u$$ is discovered last in the BFS. Then $$d(a,b)$$ is a diameter, $$t$$ is the first node discovered on that path, and the path from $$t$$ to $$u$$ does not include $$s$$.

To fix this, it's probably necessary to change "do not share edges" to "do not share vertices, as suggested by @Yuval Filmus.

Update

As @j_random_hacker points out in the comments, Lemma 1 below is not sufficient to show that $$u$$ is an endpoint of some diameter. Hence, the below proof is incomplete.

Suppose we have $$d(a, b)$$ being a diameter, but we don't know which vertices $$a$$ and $$b$$ are, so we start a BFS from some vertex $$s$$.

If $$s = a$$, then the first BFS would yield either $$b$$ or some node $$b'$$ equally distant from $$a$$, and the second would either go back to $$a$$ or to some equally distant node $$a'$$, and the scheme obviously works. Similarly, if $$s = b$$, then two BFS would work for the same reason.

Otherwise, we have $$s \neq a, b$$.

Lemma 0: Both $$a$$ and $$b$$ are leaf nodes in the tree rooted at $$s$$.

Proof 0: If they weren't leaf nodes, we could increase $$d(a,b)$$ by extending the endpoints to leaf nodes, contradicting $$d(a, b)$$ being a diameter.

Lemma 1: At least one of $$d(s,a)$$ and $$d(s, b)$$ is the largest possible value of $$d(s,u)$$ for all $$u$$.

Proof 1: Suppose we have a $$u$$ that violates the lemma. $$u$$ cannot be a descendent of $$a$$ or $$b$$ since they are leaves from Lemma 0, and $$u$$ cannot be an ancestor, since that would make it closer to $$s$$, and it would no longer be able to violate the lemma. Let $$t$$ be the lowest common ancestor of $$a$$ and $$b$$. If $$t = s$$, then both $$d(a, u)$$ and $$d(b, u)$$ would be greater than $$d(a, b)$$, a contradiction. Otherwise, $$t \neq s$$ and either $$u$$ is a descendant of $$t$$, or not.

If $$u$$ is a descendant of $$t$$, then since $$d(s,u)$$ is greater than both $$d(s, a)$$ and $$d(s, b)$$, we have $$d(t,u)$$ is greater than both $$d(t, a)$$ and $$d(t, b)$$ and thus $$d(a, u)$$ and $$d(b,u)$$ are both greater than $$d(a,b)$$, a contradiction since $$d(a,b)$$ is a diameter.

If $$u$$ is not a descendant of $$t$$, then let $$w$$ be the unique ancestor of $$u$$ such that $$d(s,t) = d(s,w)$$. We know $$w$$ exists because $$d(s,t) < d(s,u)$$. Then, we have $$d(t, b) < d(w,u) < d(t,w) + d(w,u) = d(t,u)$$ and thus $$d(a, u) = d(a, t) + d(t, u) > d(a, t) + d(t, b) = d(a, b)$$, again contradicting $$d(a, b)$$ being a diameter.

Main result: Starting from any root $$s$$ and performing a BFS will result in some $$a$$ being discovered last. Using that $$a$$ as the root of a second $$BFS$$ will result in $$b$$ being discovered last, with $$d(a,b)$$ guaranteed to be a diameter.

proof: From lemma 1, the first BFS will find an $$a$$ that is furthest from $$s$$, which is guaranteed to be one of the endpoints of a diameter. The second BFS will find that diameter, since in a tree there's exactly one simple path between any two nodes.

• Looks good, but I think the claim "then $d(t,u) > d(t,b)$" needs spelling out. Setting $v=LCA(t,u)$, we have $d(s,u)=d(s,v)+d(v,u) > d(s,v)+d(v,b)$ by the assumption on $u$, so $d(v,u) > d(v,b)$. Also $d(t,v)+d(v,b) = 2d(t,v)+d(t,b) \ge d(t,b)$ since the path $t-v$ needs to be traversed up and then back down. Thus $d(t,u) = d(t,v)+d(v,u) > d(t,v)+d(v,b) \ge d(t,b)$. Dec 23, 2020 at 0:58
• In this part of the proof, you're explicitly assuming (with the words "If the latter") that $u$ is not a descendant of $t$, meaning the path $s-u$ does not go through $t$ (or did you mean something else by "both paths"?) Also I'm thinking that Lemma 1 doesn't actually establish that the BFS started from $s$ finds an endpoint of a diameter -- this is only established in the case that there is a unique vertex having maximal distance from $s$. Also (sorry to pile on...) it doesn't look like Lemma 0 is actually used anywhere? Dec 24, 2020 at 13:25
• Ah good point; I was mistaken. I edited my answer to mention the usage of Lemma 0, and will look at the other point here. Dec 25, 2020 at 14:59
• @j_random_hacker I just changed the paragraph above "main result". Can you take another look? Dec 25, 2020 at 15:19
• Thanks, but I still don't think the statement of Lemma 1 is enough to establish that the BFS finds the endpoint of some diameter. You need to show that every vertex at maximum distance from $s$ is the endpoint of some diameter, but currently you only show that an endpoint of some diameter (or, interpreting $a-b$ to be any diameter, every diameter) is at maximum distance from $s$. It could be that the vertex at maximum distance from $s$ found by the BFS is not the endpoint of any diameter. (Unless I'm missing something.) Dec 28, 2020 at 6:34

It works because-

1. For any randomly chosen vertex $$u$$, the farthest vertex from it lies on one end of the diameter.

2. If vertex $$a$$ is one end of the diameter, the farthest vertex from it is the other end.

The first BFS takes you to one end of the diameter and the second BFS from that end takes you to the other end.

Proof

#2 is easy to see why it's true. We will see why #1 is true by contradiction. Let's suppose, the path from vertex $$a$$ to $$b$$ is the diameter of the tree and $$v$$, which is not on the diameter, is the farthest vertex from $$u$$. Also, let's assume paths $$(a,b)$$ and $$(u,v)$$ cross over at $$t$$ ($$t$$ can more generally be a path with multiple vertices). Because we don't have any cycles, all paths between vertices $$a$$, $$b$$, $$u$$ and $$v$$ pass through $$t$$.

1. By our assumptions $$d(a,b)$$ is the diameter and $$d(u,v)$$ is larger than both $$d(u,a)$$ and $$d(u,b)$$.

2. Path $$(u,t)$$ is the common piece in all paths originating from $$u$$ and hence we can deduce that $$d(v, t) > d(a, t)$$ ($$v$$ is farther away from $$t$$ as compared to $$a$$).

3. This implies that $$v$$ is also farther away from $$b$$ as compared to $$a$$ and $$d(v,b) > d(a,b)$$. (add $$d(t,b)$$ to both sides in previous step)

4. This contradicts our initial assumption that $$(a,b)$$ is a diameter because we have found a path $$(v,b)$$ which is longer. Symmetrically, we can also see why $$d(v,a) > d(a,b)$$.

5. Hence, the farthest vertex from $$u$$ must either be $$a$$ or $$b$$ if $$(a,b)$$ is indeed the diameter.

• What does this add over cs.stackexchange.com/a/68224/755? It seems like the same answer, with the same shortcomings. I think you need to explain why the statement marked 1. is always true. As I previously explained, it is not obvious, and isn't true for general graphs, so it needs some justification.
– D.W.
Mar 22, 2020 at 18:52
• On second look, not much actually apart from being slightly more concise. I will try and add justifications for both. Also, the question was asked for trees so I don't think we should worry about general graphs at least in this context. Mar 24, 2020 at 9:16

The claim is equivalent to claiming that every deepest leaf in a tree rooted at $$s$$ is an endpoint to a diameter.

Suppose $$p$$ is an arbitrary path with end points $$(a,b)$$, and that $$d$$ is some leaf that is one of the deepest. Let $$x$$ be the deepest common ancestor of $$a$$ and $$b$$.

Here is how to construct a path ending in $$d$$ that it at least as long as path $$p$$, assuming WLOG $$\text{depth}(a) \ge \text{depth}(b)$$:

   x
/ \       (b,d) is at least as long
/ \ \
a   d b

x
/ \       (a,d) is at least as long
/ / \
a d   b

/\
x  \      (a,d) is at least as long
/ \  \
a   b  d


Therefore a diameter can be constructed for every vertex $$d$$ from any other diameter.

(Edited: the previous proof only established that every diameter ended in a deepest vertex, not that every deepest vertex was part of a diameter, embarrassing mistake.)

By the definition of BFS, the distance (from the starting node) of each node explored is either equal to the distance of the previous node explored or greater by 1. Thus, the last node explored by BFS will be among those farthest from the starting node.

Thus, the algorithm of using BFS twice amounts to "Pick an arbitrary node $x$. Find the node $a$ farthest from $x$ (last node found by BFS starting from $x$). Find the node $b$ farthest from $a$ (last node found by BFS starting from $a$).", which thus finds two nodes of maximum distance from eachother.

• Thanks for the answer with the intuition. However, the "thus" in the your last sentence is not obvious. Why does that follow? Why does the node farthest from $x$ have to be one of the two nodes at maximum distance from each other? It seems like that needs some proof.
– D.W.
Jan 3, 2017 at 16:41
• I'm not sure how to construct such a proof. I feel like the converse is intuitively true: if two nodes are at maximum distance from each other, then, for any given node, one of the two is at the greatest possible distance from it. Jan 3, 2017 at 20:41
• The "intuitively true" claim isn't true in general for general graphs. See the graph in cs.stackexchange.com/a/213/755, and imagine starting the BFS from node $v$ (i.e., let $x=v$); then it will pick $a=u$ and find the node $b$ at greatest distance from $a$, but that doesn't find the two nodes of maximum distance from each other. So the claimed statement, if true, must rely on some special property of trees that doesn't hold for general graphs.
– D.W.
Jan 3, 2017 at 23:53
• Yes, but this question specifies undirected trees, which is the context I'm intuiting in. Barring cycles and directed edges makes many graph problems significantly simpler to reason about. Jan 4, 2017 at 0:41

One key thing to know is that a tree is always planar, which means it can be laid out on a plane, so often ordinary 2-dimensional thinking works. In this case, the algorithm says starting anywhere, go as far away as you can. The distance from that point to as far as you can get away from that point is the longest distance in the tree, and therefore the diameter.

This method would also work to find the diameter of a real, physical island if we defined that as the diameter of the smallest circle that would fully enclose the island.

@op, the way the cases are defined in the PDF may be a bit off.

I think that the two cases should be:

1. $$p_1$$ does not intersect with $$p_2$$, i.e. there are no common vertices between paths $$p_1$$ and $$p_2$$. In this case, define $$t$$ as the first node on $$p_2$$ discovered by the first BFS starting at $$s$$.

2. $$p_1$$ and $$p_2$$ have at least one common vertex. In this case, define $$t$$ to be the first node on $$p_2$$ discovered by the first BFS that is also on $$p_1$$.

The rest of the proof in the PDF should follow.

With this definition, the figure shown by OP falls into Case 2.

First run a DFS from a random node then the diameter of a tree is the path between the deepest leaves of a node in its DFS subtree:

• Why does this work? Dec 16, 2016 at 9:30