Sign in to watch this lesson
Advanced - Trees Ā· 4:47
Euler Tour Flattening (tin/tout) & Subtree Queries
One depth-first search stamps each vertex with tin, the moment it is entered; laid out in that order, every subtree becomes the contiguous range [tin, tout] with tout = tin + size - 1. Subtree sums then become range sums in a Fenwick tree over positions, subtree raises become range updates read back as prefix sums, and the two stamps answer 'is u an ancestor of v?' in O(1).
You will learn
- Compute tin and tout with one iterative DFS and explain why every subtree is the contiguous range [tin, tout]
- Answer subtree-sum queries with point updates by running a Fenwick tree over tin positions
- Handle 'add x to a subtree, read one vertex' with +x at tin and -x at tout + 1, and get root-path sums the same way
- Test ancestry in O(1) and tell the n-entry preorder apart from the 2n - 1 entry Euler tour