Dynamic Programming21 sections · 916 units
Open in Course

Tree Diameter - Problem Statement

CSES 1131

The diameter of a tree is the length of the longest path between any two nodes. The path can start and end anywhere. Example: In a tree with edges 11-22, 22-33, 22-44, 44-55, the diameter is 33.

The longest path is 32453 \to 2 \to 4 \to 5 (or 12451 \to 2 \to 4 \to 5). Before reading on, think about this: the longest path either stays entirely in one subtree, or it passes through some node connecting two subtrees. How would you use this?