Graph Theory37 sections · 1633 units
Open in Course

Euler Tour for LCA

(Convert tree to array)

An Euler tour converts a tree into a linear array by recording nodes during a DFS. When you enter a node, write it down. When you return to a node after visiting a child, write it down again. The result is an array of length 2n12n - 1 for a tree with nn nodes.

Each node appears multiple times. The first occurrence marks when you entered its subtree. Nodes in the same subtree appear in a contiguous block. This structure lets you reduce tree queries to array queries, which have faster algorithms. For LCA, the Euler tour enables O(1)O(1) query time after preprocessing.