Euler Tour

An Euler tour of a tree traverses each edge exactly twice - once going down and once going up. It produces a single continuous path covering all edges.

Java example:

1
2
3
4
5
6
7
8
9
void eulerTour(TreeNode root) {
  if (root == null) return;

  eulerTour(root.left);
  System.out.print(root.val + " ");
  
  eulerTour(root.right);
  System.out.print(root.val + " "); 
}

C++ example:

1
2
3
4
5
6
7
8
9
void eulerTour(TreeNode* root) {
  if (!root) return;

  eulerTour(root->left);
  cout << root->val << " ";

  eulerTour(root->right);
  cout << root->val << " ";
}

Python example:

1
2
3
4
5
6
7
8
9
def euler_tour(root):
  if root is None:
    return
  
  euler_tour(root.left)
  print(root.val, end=' ')

  euler_tour(root.right) 
  print(root.val, end=' ')

Key properties:

Visits each edge twice - down edge and up edge
Produces single continuous path
Can construct index/segment trees

Euler tour allows solving various tree problems like subtree queries efficiently. Useful technique for dynamic programming on trees.

An Euler tour in a graph is a path that traverses every edge exactly once and returns to the starting vertex. It exists only in connected graphs where either every vertex has an even degree, or exactly two vertices have an odd degree (the start and end vertices).

Algorithm

Start at a vertex: Choose any vertex as the starting point.
Visit Edges: Walk along edges, marking them as visited.
Return: Come back to the initial vertex, completing the tour.

Java Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
import java.util.Stack;

public class EulerTour {
  public static void findEulerTour(Graph graph, int start) {
    Stack<Integer> stack = new Stack<>();
    stack.push(start);

    while (!stack.isEmpty()) {
      int vertex = stack.peek();

      if (graph.hasUnvisitedEdges(vertex)) {
        stack.push(graph.nextUnvisitedEdge(vertex));
      } else {
        System.out.print(stack.pop() + " ");
      }
    }
  }
}

C++ Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
#include <stack>
#include "Graph.h"

void findEulerTour(Graph &graph, int start) {
  std::stack<int> stack;
  stack.push(start);

  while (!stack.empty()) {
    int vertex = stack.top();

    if (graph.hasUnvisitedEdges(vertex)) {
      stack.push(graph.nextUnvisitedEdge(vertex));
    } else {
      std::cout << stack.top() << " ";
      stack.pop();
    }
  }
}

Python Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
def find_euler_tour(graph, start):
    stack = [start]

    while stack:
        vertex = stack[-1]

        if graph.has_unvisited_edges(vertex):
            stack.append(graph.next_unvisited_edge(vertex))
        else:
            print(stack.pop(), end=" ")

This algorithm usually has a time complexity of (O(E)), where (E) is the number of edges. This makes it efficient for even large graphs.