Understanding the Euler Tour Technique in Trees

Tanushree

7 min read

·

May 2, 2025

--

Listen

Share

Ever struggled with tree problems that feel unnecessarily complex?

Whether it’s computing subtree sums, finding lowest common ancestors, or performing updates on entire subtrees, the standard recursive approaches can quickly become slow or cumbersome.

That’s where the Euler Tour Technique comes in — also known as Tree Flattening.

What is the Euler Tour Technique?

Think of it as a depth-first search (DFS) with extra bookkeeping. As you traverse the tree, you record the entry and exit times of each node. This simple idea allows you to map the tree structure onto a linear array, making many tree-based operations much easier — and faster — to handle with data structures like segment trees or binary indexed trees.

By flattening the tree, you can turn recursive problems into efficient range queries or updates on arrays — all without losing the structure of the original tree.

Let’s see how it works on a sample tree:

    0
   / \
  1   2
     / \
    3   4

When I say “enter” and “exit”, I mean literally this:

Enter 0
Enter 1
Exit 1
Enter 2
Enter 3
Exit 3
Enter 4
Exit 4
Exit 2
Exit 0

Yup. Every node shows up twice. Once when you arrive, once when you dip.

When Do You Use Euler Tour?

• Need subtree sum queries? Euler Tour.
• Need to update all nodes in a subtree? Euler Tour.
• Want to find LCA fast? Euler Tour + RMQ = 🔥.
• Want to pretend your tree is an array and use BITs and segment trees? Euler Tour.

import java.util.*;

public class EulerTour {
    static List<List<Integer>> tree = new ArrayList<>();
    static int[] entryTime;
    static int[] exitTime;
    static int timer = 0;

    public static void main(String[] args) {
        int n = 5; // Nodes are 0-indexed
        entryTime = new int[n];
        exitTime = new int[n];

        // Initialize the adjacency list
        for (int i = 0; i < n; i++) {
            tree.add(new ArrayList<>());
        }

        // Edges of a simple tree
        addEdge(0, 1);
        addEdge(0, 2);
        addEdge(2, 3);
        addEdge(2, 4);

        // Flatten the tree from root (node 0)
        eulerTour(0, -1);

        // Showoff: Entry & Exit times
        for (int i = 0; i < n; i++) {
            System.out.println("Node " + i + " ➜ Entry: " + entryTime[i] + ", Exit: " + exitTime[i]);
        }
    }

    static void addEdge(int u, int v) {
        tree.get(u).add(v);
        tree.get(v).add(u); // Because it’s undirected
    }

    static void eulerTour(int node, int parent) {
        entryTime[node] = timer++;  // Record entry time and increment timer
        for (int neighbor : tree.get(node)) {
            if (neighbor != parent) {
                eulerTour(neighbor, node);  // Recursively explore neighbors
            }
        }
        exitTime[node] = timer - 1;  // Record exit time after visiting all children
    }
}

What’s Happening Here?

• entryTime[node] = When we step into node.
• exitTime[node] = When we say "peace out" after visiting its kids.
• timer: A global stopwatch that ticks forward every time we enter or exit a node—faster than your heart rate during a live coding interview.

The real magic?
Once you’ve done the tour, the entire subtree of any node lives between its entryTime and exitTime in this flattened sequence.

Which means:

Subtree = Contiguous Range — perfect for segment tree or BIT operations.

Real-World Application: Subtree Sum Queries

You can use a Segment Tree or Fenwick Tree (BIT) on an array built using this tour. Every subtree becomes a range.

You are given a tree with n nodes. Each node has a value. You need to answer two types of operations efficiently:

1. update(u, val) — Set the value at node u to val.
2. query(u) — Return the sum of values in the subtree rooted at node u.

Step 1: Flatten the Tree Using DFS (Euler Tour)

Step 2: Use a Segment Tree to Handle Range Queries and Updates

Step 3: Use the Segment Tree to Perform Operations

import java.util.*;

// Main class that implements the Euler Tour Technique with a Segment Tree
public class EulerTourWithSegmentTree {
    // Tree representation (adjacency list)
    static List<List<Integer>> adjacencyList = new ArrayList<>();
    // Arrays to store the entry and exit times for each node during DFS traversal
    static int[] entryTime, exitTime, nodeValues;
    // Timer to maintain the DFS time (used for entry and exit times)
    static int timer = 0;

    public static void main(String[] args) {
        // Number of nodes (0-indexed)
        int n = 5;

        // Initialize arrays to hold entry and exit times, and the node values
        entryTime = new int[n];
        exitTime = new int[n];
        nodeValues = new int[n]; // Values at each node

        // Initialize the tree with n nodes (empty adjacency lists)
        for (int i = 0; i < n; i++) {
            adjacencyList.add(new ArrayList<>());
        }

        // Adding edges to form the tree (undirected)
        addEdge(0, 1); // Edge between node 0 and node 1
        addEdge(0, 2); // Edge between node 0 and node 2
        addEdge(2, 3); // Edge between node 2 and node 3
        addEdge(2, 4); // Edge between node 2 and node 4

        // Perform Euler Tour to record entry and exit times of each node
        // The timer starts from 0. The entry/exit times will be 0-indexed.
        performEulerTour(0, -1); // Start DFS from the root node (0)

        // Set initial values for each node (this could be any values)
        nodeValues[0] = 10;
        nodeValues[1] = 5;
        nodeValues[2] = 15;
        nodeValues[3] = 7;
        nodeValues[4] = 8;

        // Now, flatten the tree based on entry times
        // The flattened array represents node values ordered by their entry time.
        // The size of this flattened array should be equal to the number of nodes.
        int[] flattenedValues = new int[n];
        for (int i = 0; i < n; i++) {
             // Place the value of node 'i' at the index corresponding to its entry time
            flattenedValues[entryTime[i]] = nodeValues[i];
        }

        // Create an iterative segment tree with the flattened values
        SegmentTree segmentTree = new SegmentTree(n); // Renamed class instantiation
        segmentTree.build(flattenedValues); // Build the segment tree

        // Query the sum of the subtree rooted at node 2
        // The subtree of node 2 corresponds to the range [entryTime[2], exitTime[2]]
        // in the flattened array.
        int subtreeSum = segmentTree.query(entryTime[2], exitTime[2]);
        System.out.println("Subtree sum of node 2: " + subtreeSum);

        // Update the value at node 2 (set it to 20)
        // To update the value of node 2, we update the element at entryTime[2]
        // in the flattened representation.
        segmentTree.update(entryTime[2], 20); // Update node 2's value to 20

        // Query again after the update
        subtreeSum = segmentTree.query(entryTime[2], exitTime[2]);
        System.out.println("Updated subtree sum of node 2: " + subtreeSum);
    }

    // Utility to add edges to the tree (undirected)
    static void addEdge(int u, int v) {
        adjacencyList.get(u).add(v);
        adjacencyList.get(v).add(u); // Undirected graph
    }

    // DFS-based Euler Tour to fill entry and exit times
    static void performEulerTour(int currentNode, int parentNode) {
        entryTime[currentNode] = timer++;  // Record entry time for the node
        for (int neighborNode : adjacencyList.get(currentNode)) {
            if (neighborNode != parentNode) {
                performEulerTour(neighborNode, currentNode);  // Recursively visit neighbors (DFS)
            }
        }
        exitTime[currentNode] = timer - 1;  // Record exit time after visiting all children
    }
}

// Iterative Segment Tree class to support range sum queries and point updates
class SegmentTree { // Renamed from SegmentTreeIterative
    private int[] tree; // Array representing the segment tree
    private int n;      // Size of the original array (number of leaves)

    // Constructor to initialize the segment tree
    public SegmentTree(int size) {
        this.n = size;
        // The tree array size is 2*n for an iterative segment tree using 0-based indexing for leaves starting at n.
        this.tree = new int[2 * n];
    }

    // Build the segment tree with the given array values iteratively
    public void build(int[] values) {
        // Copy initial values to the leaves of the segment tree (indices n to 2n-1)
        for (int i = 0; i < n; i++) {
            tree[n + i] = values[i];
        }
        // Build the rest of the tree by calculating sums upwards
        for (int i = n - 1; i > 0; i--) {
            tree[i] = tree[2 * i] + tree[2 * i + 1];
        }
    }

    // Update the value at index `idx` in the original array (and propagate to the tree)
    public void update(int idx, int value) {
        // Go to the leaf node corresponding to the index
        idx += n;
        tree[idx] = value; // Update the leaf value
        // Propagate the update upwards to the root
        while (idx > 1) {
            // Update the parent node's value (sum of children)
            // idx^1 gives the sibling index (2*i+1 if idx is 2*i, and 2*i if idx is 2*i+1)
            tree[idx / 2] = tree[idx] + tree[idx ^ 1];
            idx /= 2; // Move to the parent node
        }
    }

    // Query the sum in the range [L, R] (inclusive) iteratively
    public int query(int L, int R) {
        int res = 0;
        // Adjust L and R to the segment tree indices for the range [L, R]
        L += n; // Start index in the tree array
        R += n; // End index in the tree array

        // Traverse up the tree
        while (L <= R) {
            // If L is a right child (odd index), its range is included. Add its value and move to the next node.
            if ((L % 2) == 1) {
                res += tree[L];
                L++;
            }
            // If R is a right child (odd index), its range is included. Add its value and move to the previous node.
            if ((R % 2) == 0) {
                res += tree[R];
                R--;
            }
            // Move up to the parent nodes
            L /= 2;
            R /= 2;
        }
        return res;
    }
}

Time Complexity:

• DFS (Euler Tour): O(n)
• Segment Tree Build: O(n)
• Query/Update on Segment Tree: O(log n)

When you realize trees are just arrays in disguise.

Conclusion:

The Euler Tour Technique is a game-changer for tree problems. Whether you need subtree queries, LCA, or subtree updates, Euler Tour flattens your tree and makes everything feel like an array problem.

And when trees become arrays? Well, it’s smooth sailing from there.

For a complete look at Segment Tree implementation details, check out my blog post: Segment Trees: The Secret Weapon for Range Queries