Euler tour of tree has been already discussed which flattens the hierarchical structure of tree into array which contains exactly 2*N-1 values. In this post, the task is to prove that the degree of Euler Tour Tree is 2 times the number of nodes minus one. Here degree means the total number of nodes get traversed in Euler Tour.
Examples:
Input:
Output: 15
Input:
Output: 17
Explanation:
Using Example 1:
where
It can be seen that each node’s count in Euler Tour is exactly equal to the out-degree of node plus 1.
Mathematically, it can be represented as:
Where,
Total represents total number of nodes in Euler Tour Tree node_i represents ith node in given Tree @N represents the total number of node in given Tree@Out_D_e_g[node_i] represents number of child of node_i
![$\displaystyle Total=\sum_{node_i=1}^{N} Out_D_e_g[node_i]+1$](https://neveropen.co.uk/wp-content/uploads/2023/11/wardslaus_rubhabha_quicklatex.com-95fca324e8c1af4e6a6f9a44d6cfc20f_l3.png "Rendered by QuickLaTeX.com")
![$\displaystyle Total= N + \sum_{node_i=1}^{N} Out_D_e_g[node_i]$](https://neveropen.co.uk/wp-content/uploads/2023/11/dominic_rubhabha_quicklatex.com-1dd2acb3194f14fea7d944e3f9c559c0_l3.png "Rendered by QuickLaTeX.com")
Implementation:
C++
// C++ program to check the number of nodes// in Euler Tour tree.#include <bits/stdc++.h>using namespace std;#define MAX 1001// Adjacency list representation of treevector<int> adj[MAX];// Function to add edges to treevoid add_edge(int u, int v){ adj[u].push_back(v);}// Program to check if calculated Value is // equal to 2*size-1void checkTotalNumberofNodes(int actualAnswer, int size){ int calculatedAnswer = size; // Add out-degree of each node for (int i = 1; i <= size; i++) calculatedAnswer += adj[i].size(); if (actualAnswer == calculatedAnswer) cout << "Calculated Answer is " << calculatedAnswer << " and is Equal to Actual Answer\n"; else cout << "Calculated Answer is Incorrect\n";}int main(){ // Constructing 1st tree from example int N = 8; add_edge(1, 2); add_edge(1, 3); add_edge(2, 4); add_edge(2, 5); add_edge(3, 6); add_edge(3, 7); add_edge(6, 8); // Out_deg[node[i]] is equal to adj[i].size() checkTotalNumberofNodes(2 * N - 1, N); // clear previous stored tree for (int i = 1; i <= N; i++) adj[i].clear(); // Constructing 2nd tree from example N = 9; add_edge(1, 2); add_edge(1, 3); add_edge(2, 4); add_edge(2, 5); add_edge(2, 6); add_edge(3, 9); add_edge(5, 7); add_edge(5, 8); // Out_deg[node[i]] is equal to adj[i].size() checkTotalNumberofNodes(2 * N - 1, N); return 0;} |
Java
// Java program to check the number of nodes// in Euler Tour tree.import java.util.*;class GFG { static final int MAX = 1001; // Adjacency list representation of tree static Vector<Integer>[] adj = new Vector[MAX]; // Function to add edges to tree static void add_edge(int u, int v) { adj[u].add(v); } // Program to check if calculated Value is // equal to 2*size-1 static void checkTotalNumberofNodes(int actualAnswer, int size) { int calculatedAnswer = size; // Add out-degree of each node for (int i = 1; i <= size; i++) calculatedAnswer += adj[i].size(); if (actualAnswer == calculatedAnswer) System.out.print("Calculated Answer is " + calculatedAnswer + " and is Equal to Actual Answer\n"); else System.out.print("Calculated Answer is Incorrect\n"); } // Driver Code public static void main(String[] args) { for (int i = 0; i < MAX; i++) adj[i] = new Vector<Integer>(); // Constructing 1st tree from example int N = 8; add_edge(1, 2); add_edge(1, 3); add_edge(2, 4); add_edge(2, 5); add_edge(3, 6); add_edge(3, 7); add_edge(6, 8); // Out_deg[node[i]] is equal to adj[i].size() checkTotalNumberofNodes(2 * N - 1, N); // clear previous stored tree for (int i = 1; i <= N; i++) adj[i].clear(); // Constructing 2nd tree from example N = 9; add_edge(1, 2); add_edge(1, 3); add_edge(2, 4); add_edge(2, 5); add_edge(2, 6); add_edge(3, 9); add_edge(5, 7); add_edge(5, 8); // Out_deg[node[i]] is equal to adj[i].size() checkTotalNumberofNodes(2 * N - 1, N); }}// This code is contributed by Rajput-Ji |
Python3
# Python3 program to check the number # of nodes in Euler Tour tree.MAX = 1001;# Adjacency list representation of treeadj = [list() for _ in range(MAX)] # Function to add edges to treedef add_edge(u, v): l1 = adj[u] l1.append(v) adj[u] = l1;# Program to check if calculated Value is# equal to 2*size-1def checkTotalNumberofNodes(actualAnswer, size) : calculatedAnswer = size; # push out-degree of each node for i in range(1, size + 1): calculatedAnswer += len(adj[i]); if (actualAnswer == calculatedAnswer): print("Calculated Answer is", calculatedAnswer, "and is Equal to Actual Answer") else: print("Calculated Answer is Incorrect");# Driver Code # Constructing 1st tree from exampleN = 8;add_edge(1, 2);add_edge(1, 3);add_edge(2, 4);add_edge(2, 5);add_edge(3, 6);add_edge(3, 7);add_edge(6, 8);# Out_deg[node[i]] is equal to adj[i].CountcheckTotalNumberofNodes(2 * N - 1, N);# clear previous stored treefor i in range(N + 1): adj[i] = [] # Constructing 2nd tree from exampleN = 9;add_edge(1, 2);add_edge(1, 3);add_edge(2, 4);add_edge(2, 5);add_edge(2, 6);add_edge(3, 9);add_edge(5, 7);add_edge(5, 8);# Out_deg[node[i]] is equal to adj[i].CountcheckTotalNumberofNodes(2 * N - 1, N);# This code is contributed by phasing17 |
C#
// C# program to check the number // of nodes in Euler Tour tree.using System;using System.Collections.Generic;class GFG { static readonly int MAX = 1001; // Adjacency list representation of tree static List<int>[] adj = new List<int>[MAX]; // Function to add edges to tree static void add_edge(int u, int v) { adj[u].Add(v); } // Program to check if calculated Value is // equal to 2*size-1 static void checkTotalNumberofNodes(int actualAnswer, int size) { int calculatedAnswer = size; // Add out-degree of each node for (int i = 1; i <= size; i++) calculatedAnswer += adj[i].Count; if (actualAnswer == calculatedAnswer) Console.Write("Calculated Answer is " + calculatedAnswer + " and is Equal to Actual Answer\n"); else Console.Write("Calculated Answer " + "is Incorrect\n"); } // Driver Code public static void Main(String[] args) { for (int i = 0; i < MAX; i++) adj[i] = new List<int>(); // Constructing 1st tree from example int N = 8; add_edge(1, 2); add_edge(1, 3); add_edge(2, 4); add_edge(2, 5); add_edge(3, 6); add_edge(3, 7); add_edge(6, 8); // Out_deg[node[i]] is equal to adj[i].Count checkTotalNumberofNodes(2 * N - 1, N); // clear previous stored tree for (int i = 1; i <= N; i++) adj[i].Clear(); // Constructing 2nd tree from example N = 9; add_edge(1, 2); add_edge(1, 3); add_edge(2, 4); add_edge(2, 5); add_edge(2, 6); add_edge(3, 9); add_edge(5, 7); add_edge(5, 8); // Out_deg[node[i]] is equal to adj[i].Count checkTotalNumberofNodes(2 * N - 1, N); }}// This code is contributed by PrinciRaj1992 |
Javascript
<script>// Javascript program to check the number // of nodes in Euler Tour tree.var MAX = 1001;// Adjacency list representation of treevar adj = Array.from(Array(MAX), ()=>Array());// Function to add edges to treefunction add_edge(u, v) { adj[u].push(v);}// Program to check if calculated Value is// equal to 2*size-1function checkTotalNumberofNodes(actualAnswer, size) { var calculatedAnswer = size; // push out-degree of each node for (var i = 1; i <= size; i++) calculatedAnswer += adj[i].length; if (actualAnswer == calculatedAnswer) document.write("Calculated Answer is " + calculatedAnswer + " and is Equal to Actual Answer<br>"); else document.write("Calculated Answer " + "is Incorrect<br>");}// Driver Codefor (var i = 0; i < MAX; i++) adj[i] = []; // Constructing 1st tree from examplevar N = 8;add_edge(1, 2);add_edge(1, 3);add_edge(2, 4);add_edge(2, 5);add_edge(3, 6);add_edge(3, 7);add_edge(6, 8);// Out_deg[node[i]] is equal to adj[i].CountcheckTotalNumberofNodes(2 * N - 1, N);// clear previous stored treefor (var i = 1; i <= N; i++) adj[i] = [] // Constructing 2nd tree from exampleN = 9;add_edge(1, 2);add_edge(1, 3);add_edge(2, 4);add_edge(2, 5);add_edge(2, 6);add_edge(3, 9);add_edge(5, 7);add_edge(5, 8);// Out_deg[node[i]] is equal to adj[i].CountcheckTotalNumberofNodes(2 * N - 1, N);// This code is contributed by itsok.</script> |
Output
Calculated Answer is 15 and is Equal to Actual Answer Calculated Answer is 17 and is Equal to Actual Answer
Time complexity: O(N)
Auxiliary space: O(MAX)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
