Graph Theory37 sections · 1633 units
Open in Course

Example: Count Subtree Sizes

Simplest aggregation problem

How many nodes are in the subtree rooted at each node?

For leaves: answer is 11 (themselves). For internal nodes: answer is 1 + sum ext{size}[ ext{child}]. Add 11 for yourself, plus the sizes of all child subtrees. This shows the aggregation pattern: compute children first, then combine. The recurrence is simple but appears everywhere in tree DP. If you understand subtree size, you understand the foundation.