Graph Theory37 sections · 1633 units
Open in Course

Subtrees as Ranges

(Why this works)

Here is what matters: node uu is in vv's subtree if and only if tin[v] <= tin[u] <= tout[v]. Why?

DFS enters vv before any descendant and exits vv after all descendants. The interval [tin[v], tout[v]] contains all entry times of nodes in vv's subtree. If you store node values at position tin[v] in an array, every subtree becomes a contiguous range. Subtree queries become range queries.