Algorithms / Euler Tour Subtree Ranges
Least You Need to Know: Euler Tours, Subtree Intervals, and Flattened Trees
An Euler-tour-style entry order can flatten a rooted tree so each subtree becomes a contiguous interval in an array. That converts many subtree problems into familiar range-query problems.
Least you need to know
- DFS entry times record when each node is first visited.
- A subtree of node
uoccupies a contiguous interval in entry order. - Flattening lets Fenwick trees or segment trees answer subtree aggregates.
- Subtree size determines the interval length in simple entry-order flattening.
- Tree-to-array reductions are common preprocessing tricks.
Key notation
- tin[u] — entry time of node
uin DFS order - subtree_size[u] — number of nodes in the subtree rooted at
u - [tin[u], tin[u] + size[u]) — array interval covering the subtree in flattened order
Worked example
- Suppose DFS visits nodes in entry order
1, 2, 4, 5, 3, 6. - If node
2has descendants4and5, then its subtree occupies the contiguous block2, 4, 5in that entry list. - A subtree-sum query can then become a range-sum query on that block.
- This is why Euler tours pair naturally with Fenwick and segment trees.
Common mistakes
- Students sometimes mix entry times with full walk positions from a different Euler-tour convention.
- The interval formula depends on which flattening variant is used.
- The contiguous-range trick works for rooted subtrees, not arbitrary connected subgraphs.
How to recognize it
- A tree problem asks for repeated subtree sums, counts, or updates.
- The solution hints at flattening a tree into an array.
- A later data structure wants contiguous intervals.
Next recommended lesson
Continue through this topic with Least You Need to Know: Fast/Slow Pointers, Middle Nodes, and Cycle Entry.
Least You Need to Know: Fast/Slow Pointers, Middle Nodes, and Cycle EntryRelated lessons
Keep going with nearby lessons in the same topic.