Senior LevelData Structures & Algorithms
How does an Euler Tour flatten a tree for efficient subtree queries?
ā Interview Prompt: Explain Euler Tour (DFS entry/exit times), subtree flattening, converting tree queries to range queries on arrays.
An Euler Tour assigns each node an entry time (tin) and exit time (tout) via DFS. The subtree of any node $u$ corresponds exactly to the range [tin[u], tout[u]] in the tour array.
Why It Works:
During DFS, all nodes in the subtree of $u$ are visited between entering and leaving $u$.
Applications:
ā¢
Subtree sum/min/max ā range query on
[tin[u], tout[u]] of the tour array.ā¢
Combined with Segment Tree: $O(\log N)$ subtree update/query.
ā¢
LCA via Euler Tour + Sparse Table: $O(N \log N)$ preprocessing, $O(1)$ LCA.
Code Implementation Example
typescript
function eulerTour(
root: number, adj: number[][], n: number
): { tin: number[]; tout: number[]; order: number[] } {
const tin = new Array(n), tout = new Array(n), order: number[] = [];
let timer = 0;
function dfs(u: number, parent: number): void {
tin[u] = timer;
order[timer++] = u; // record entry
for (const v of adj[u]) {
if (v !== parent) dfs(v, u);
}
tout[u] = timer - 1; // last index in subtree
}
dfs(root, -1);
return { tin, tout, order };
}
// After Euler Tour:
// - Subtree of u = range [tin[u], tout[u]] in 'order' array
// - Apply Segment Tree on 'order' for O(log N) subtree queries!š”Euler Tour assigning entry/exit times ā enabling subtree range queries.
šÆ Interview Key Takeaway
Euler Tour maps subtree problems to 1D range problems. Combine with Segment Tree for O(log N) subtree updates/queries. Also enables O(1) LCA with Sparse Table.
#DSA#Euler Tour#Tree#DFS#Senior
Back to all Data Structures & Algorithms Questionsā