Euler Tour of a Tree

An Euler-tour representation turns a rooted tree into an array so that every rooted subtree occupies one continuous interval. This is the bridge between tree problems and range-query data structures: after flattening, a subtree sum becomes an array range sum. The name has several conventions. Here we record each vertex once, on entry, and store an inclusive exit boundary. This is a DFS preorder flattening, not an Eulerian walk that uses each edge once. The longer Euler walk used for LCA repeats vertices and is a different representation.

Prerequisites: Rooted trees, DFS, stack frames, and array indexing.

Build the idea

1. 1. Decide exactly what your timestamps mean. Root the tree at vertex 1 and visit adjacency lists in input order. On first entering v, set tin[v] to the next unused array position and put v at that position. Explore every child completely before continuing with its next sibling. When v finishes, set tout[v] to the current timer without incrementing it. With this convention subtree(v) is exactly the inclusive interval [tin[v], tout[v]]. A leaf has equal entry and exit boundaries. All positions use 1-based indexing.
2. 2. Work through a branching example. Take edges 1–2, 1–3, 2–4, 2–5. The preorder is [1,2,4,5,3]. Vertex 2 enters at position 2, its children occupy positions 3 and 4, and it finishes with tout[2]=4. Its subtree is [2,4], containing precisely vertices 2,4,5. The root has [1,5]. Vertex 3 has [5,5]. Notice that labels need not be consecutive inside a subtree; preorder positions are consecutive even when labels are not.
3. 3. Why the interval property holds. Once DFS enters v, it explores only descendants of v until it returns to the parent. No vertex outside that subtree can enter in the meantime. Conversely, every descendant is reached before v finishes because the tree is connected and has a unique path to each vertex. Therefore there are no gaps or foreign vertices in the interval. Its length is also the subtree size: tout[v]−tin[v]+1. Vertex u is an ancestor of v, allowing equality, exactly when tin[u]≤tin[v]≤tout[u].
4. 4. Simulate entry and exit reliably. The runnable example uses explicit stack frames (vertex, parent, exiting) rather than recursive calls. An entry frame records tin and pushes an exit frame below its child frames. Children are pushed in reverse adjacency order so the resulting traversal matches recursive DFS. The exit frame runs only after every descendant has finished. Recording tout immediately after pushing children would be wrong: the timer has not advanced through them yet.
5. 5. Connect flattening to queries. If vertex v stores a value, put that value at flat[tin[v]]. A Fenwick tree supports point changes and subtree-sum queries in O(log N); a lazy segment tree also supports adding a value to an entire subtree. For example assigning values equal to labels gives flattened values [1,2,4,5,3], so subtree(2) sums to 11. These structures do not alter the flattening, only the values stored at its positions. Changing tree edges or changing the root generally requires rebuilding the intervals.
6. 6. Read the sample output. Each line prints vertex, entry position, and inclusive exit boundary. The code also prints the preorder array. It assumes a valid undirected tree with N≥1. The explicit stack keeps a path of arbitrary length from overflowing the C++ call stack. For the single-vertex tree the order is [1] and its interval is [1,1].

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<vector>
#include<tuple>
using namespace std;
int main(){
    int n;
    cin>>n;
    vector<vector<int>>g(n+1);
    for(int i=1,u,v;i<n;i++){
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    // Entry positions flatten each rooted subtree into one inclusive interval.
    vector<int>tin(n+1),tout(n+1),order(n+1);
    vector<tuple<int,int,bool>>st;
    st.push_back({1,0,false});
    int timer=0;
    while(!st.empty()){
        auto[v,p,exiting]=st.back();
        st.pop_back();
        // Exit runs after all descendants, so timer is the subtree boundary.
        if(exiting){
            tout[v]=timer;
            continue;
        }
        tin[v]=++timer;
        order[timer]=v;
        st.push_back({v,p,true}); // Exit after all child subtrees.
        // Reverse pushes preserve adjacency-list order when using a LIFO stack.
        for(int i=(int)g[v].size()-1;i>=0;i--){
            if(g[v][i]!=p){
                st.push_back({g[v][i],v,false});
            }
        }
    }
    for(int v=1;v<=n;v++){
        cout<<v<<' '<<tin[v]<<' '<<tout[v]<<'\n';
    }
    for(int i=1;i<=n;i++){
        cout<<order[i]<<(i==n?'\n':' ');
    }
}

Complexity analysis

Flattening takes O(N) time and O(N) auxiliary space: every vertex enters and exits once, and each adjacency-list edge is inspected a constant number of times. An ancestor test takes O(1). Later range-query costs depend on the chosen array data structure.

Example input and output

N, followed by N−1 undirected edges. Output N lines v tin[v] tout[v], then the preorder. Root is 1.

Input

5
1 2
1 3
2 4
2 5

Output

1 1 5
2 2 4
3 5 5
4 3 3
5 4 4
1 2 4 5 3

Vertex 2 occupies positions 2 through 4; no vertex from the other root branch appears in that interval.

Practical applications

Use flattening for subtree sums, subtree updates, ancestor checks, offline queries, and the DFS ordering used by virtual trees. Study Fenwick trees and segment trees to turn the representation into dynamic queries.

Check your understanding

With inclusive exit boundaries, what is the size of subtree(v)?

Put it into practice

Add vertex values and answer subtree sums using prefix sums when values never change.