Graph Theory37 sections · 1633 units
Open in Course

Path Problems on Trees

Paths through nodes

Some problems ask for the best path in a tree. A path is a sequence of nodes connected by edges. Core idea: every path has a highest node (the node closest to the root that is on the path). Consider each node as the potential highest node.

For node vv, the best path through vv combines the best paths going down into different child subtrees. You pick the two best downward paths and connect them through vv.