Diameter of Tree

PHOTO

Mon Jan 10 2022 06:56:11 GMT+0000 (Coordinated Universal Time)

Saved by @vaibhav_55

   //code of this is same as the single source shortest path discussed above we just need run that algo 2 times.

Following,is the algo to find the diameter of a tree. Step 1: choose any random node and run dfs from it and find the farthest node from it. Step 2:from the found node again run the dfs and find the again the farthest node. Step 3:now,the distance of the farthest node found in 2nd step from the node from which we ran dfs in 2nd step is diameter.

Save snippets that work from anywhere online with our extensions

Available in the Chrome Web Store

Get Firefox Add-on

Get VS Code extension

Comments

More like this

Graphs

@vaibhav_55

Dfs No of Connected Components Single source shortest path (on trees) Bipartite Graph test cycle detection in undirected graph Cycle detection in directed graph In-Out time of nodes Diameter of Tree Calculating the sizeof subtree in O(n) Bfs single shortest path using bfs Articulation point 🚩🚩🚩 Bridges in graph 🚩🚩🚩 Topological Sort 🚩🚩🚩 Shortest Path in DAG🚩🚩 Dijkstra Algorithm (single source shortest path)🚩🚩 Primes Algo for MST🚩🚩 Disjoint Set Union🚩🚩🚩 Kruskal's Algorithm for MST 🚩🚩🚩

Browse more snippets >>