The Tree Data Structure is a special graph with the following characteristics:

  • has E = V - 1 (any O(V + E) algorithm is O(V))
  • it has no cycle
  • it is connected
  • there exists one unique path from any pair of vertices

Diameter of a Tree Edit

The diameter of a graph is defined as the greatest distance between any pair of vertices. To find the diameter of a graph, we first find the shortest path between each pair of vertices. The greatest length of any of these paths is the diameter of the graph. For general graph, we may need O(V3) Floyd Warshall's Algorithm. However, if the given graph is a tree, the problem is simpler: do DFS/BFS from any node s to find furthest vertex x, then do DFS/BFS one more time from vertex x to get the true furthest vertex y from x. The length of the unique path along x to y is the diameter of that tree. This solution only requires two calls of O(V) graph traversal algorithm.