Diameter of a Tree

Definition of a Tree

Tree is a sub-type of a Graph, which every node(except root node) has exactly one parent. If tree edge is undirectional, then every node can be root node.

One important feature of a tree is that, there exists only one unique path between arbitrary nodes.

Diameter of a Tree

Diameter of a tree is the longest path between nodes in the tree.

Figure of a Tree Datastructure. From https://en.wikipedia.org/wiki/File:Tree_(computer_science).svg

In the figure above, path between node4 and node5 is 6. This is the longest path in the node, so the diameter of the tree is 6.

Algorithm of getting Diameter of a Tree

To get the diameter of a Tree, you might think we have to iterate every node by setting the path-start-point. This algorithm may work, but it's time-complexity would be $O(N^2)$, where $N$ is number of nodes.

Actually, there is a $O(N)$ algorithm to get the diameter of a Tree.

1. Pick an arbitrary node(node u) in the tree.

2. Using BFS/DFS algorithm, get the farthest node(node v) from node u.

3. Using BFS/DFS algorithm, get the farthest node(node w) from node v.

4. Path length between node v and node w is the diameter of a tree.

Proof of the algorithm

To prove this algorithm, we have to use two important feature of a undirectional tree: Every node can be a root There exists only one unique path between arbitrary nodes

Let's set node u as the root of the tree. Then we can draw the tree as following: Let's assume node u is included in the path (v, w).

node v is the farthest point from node u. node w is the farthest point from node u.

What if there exists a node w' that (v, w') is the diameter of the tree?

This can't be possible because node w is the farthest point from v, in other words w is the farthest point from u.

$$d(v, w) = d(v, u)+d(u,w) \\~\\ d(v, w') = d(v, u)+d(u, w') <d(v,u)+d(u,w)=d(v,w)$$

What if there exists a node v' that (v', w) is the diameter of the tree?

This is similar to the upper case. This case is impossible.

$$d(v, w) = d(v,u)+d(u,w) \\~\\ d(v',w)= d(v',u)+d(u,w)<d(v,u)+d(u,w)$$

What if node u is not at the path between node v and node w?

I supposed a strong assumption when proving the algorithm. What if this assumption is not satisfied?

Actually this doesn't matter because we can set a new root node as follows:

Node u' is closest node to node u, that is on the path between node v and node w. We can prove the algorithm with node u'.

References

[1] https://en.wikipedia.org/wiki/Tree_(abstract_data_type)

[2] https://koosaga.com/14