Tree Diameter
AlgorithmsEasyCompute maximum path lengths in tree networks utilizing dual DFS sweeps.
Alt+Shift+D
Configuration Panel
Adjust tree structures on the canvas and run the diameter calculator. Farthest leaf paths are highlighted in yellow.
Tree Layout Canvas
Double-click empty canvas to create root, select node to add child or delete.
Time Complexity
O(N) dual DFS passes
Auxiliary Space Complexity
O(N) recursion stack size
Conceptual Overview
The Diameter of a tree is the maximum length of a simple path between any two vertices in the tree (the maximum distance between any two nodes).
Algorithm Mechanism
Can be solved using two DFS sweeps on undirected trees: first DFS from an arbitrary node locates the farthest leaf y; second DFS from y locates the farthest node z. The path y-z is the diameter.
Source: CP-Algorithms reference guide