Graph Theory37 sections · 1633 units
Open in Course

What is an Euler Tour

(DFS traversal order)

An Euler tour records the order you visit nodes during DFS. Start at the root, visit each child's subtree, then backtrack. If you write down every node you see (including when you return to it), you get a sequence.

For tree with nodes 11 (root), 22, 33 as children of 11: the tour is [1,2,1,3,1][1, 2, 1, 3, 1]. This sequence captures the tree's structure. Every subtree appears as a contiguous block. That contiguity is what makes Euler tour so useful for range queries.