Euler tour of a tree in C++

In this tute, we will discuss the Euler tour of a tree in C++. Before entering into the topic, let’s see an intro about trees.

Euler Tour:

Euler Tour of a tree is defined as the path traversed in the graph such that each vertex is added to the path as it is visited. This includes both entering from parent to child and child to parent traversal. The tour starts from the root and ends at the root after traversing all the nodes. Let’s see an example.

Euler tour of a tree in C++

The graph traversal technique used here is the Depth First Search(DFS).

 

Algorithm:

  1. Firstly, the route starts at the root node and the root node is added.
  2. Then goes to the leftmost child and the child is added in the route.
  3. This goes recursively till a leaf is reached.
  4. When the function is traced back to its parent from the leaf node, the parent is again added to the route.
  5. Only after this, the traversal goes to the next child.
  6. Finally, the Euler tour ends at the root.

 

Note: The Euler tour always has 2*N – 1 nodes in the route. Where N is the total number of nodes in the tree.

 

Below is the implementation for finding the Euler tour using Dept First Search(DFS).

 

Output:

#include<bits/stdc++.h>
using namespace std;

vector<int> g[1000];
vector<int> tour;

void add_edge(int from, int to)
{
    g[from].push_back(to);
    g[to].push_back(from);
}

void dfs(int cur, bool visited[])
{
    tour.push_back(cur);
    visited[cur] = true;

    for(auto adj: g[cur])
        if(!visited[adj]) {
            dfs(adj, visited);
            tour.push_back(cur);
        }
}

void eulerTour(int n, int root)
{
    bool visited[n];
    fill(visited, visited+n, false);

    dfs(root, visited);

    cout<<"Euler Tour: ";
    for(int i=0 ; i<2*n-1 ; ++i)
        cout<<tour[i]<<' ';
    cout<<endl;
}

int main()
{
    for(int i=0 ; i<10 ; ++i) g[i].clear();  // Clears all the edges

    add_edge(0, 1);
    add_edge(0, 2);
    add_edge(1, 3);
    add_edge(1, 4);
    add_edge(2, 5);
    add_edge(2, 6);
    add_edge(5, 7);
    add_edge(5, 8);
    add_edge(5, 9);

    eulerTour(10, 0);

    return 0;
}

 

Time Complexity:

The time complexity is O(n) since all the nodes of the tree are visited once. Extra 2*N-1 space is used to store the Euler tour which can be written as O(n) auxiliary space.

 

Also, read:

Leave a Reply