Graph Theory37 sections · 1633 units
Open in Course

Rooted vs Unrooted Trees

Picking a root matters

An unrooted tree has no designated root. To use subtree DP, pick any node as root (often node 11). Once rooted, edges have direction (parent to child). Subtrees are well-defined. Some problems care about the root choice (path queries).

Others do not (subtree sizes). If the problem is symmetric, any root works. The choice of root changes which nodes are ancestors vs descendants, but not the tree structure itself.