 # LCA and Euler Tour Tree

Can anyone explain the how the size of an Euler Tour Tree(ETT) array is 2*no.of vertices.
please read the ETT of type 3 in this LCA, in ETT of type 2, it is quite clear that we need double the space of total vertices to store the ETT as all vertices are added exactly twice(one for entry and one for exit).

In ETT of type 3, it is mentioned that a vertice is added each time it is visited, now my conclusion is that, a node will be added exactly (1 + no.of children it has), now i am not able to deduce how only 2 * total vertices are needed, as claimed in this article.

1 Like

Think of it this way:

An Euler tour is the path you follow if you draw the given tree without lifting your pencil. You start from the root and in each move of your pencil you will add exactly one node to the ETT, the next one. So total number of elements will be equal to 2 * (n - 1) + 1 = 2 * n - 1 because you will visit each edge of the tree exactly two times (once going downwards and once upwards) plus one for your initial visit of the root.

Hope that helps!

3 Likes

You can refer to this link for getting a pictorial view of what the author of the codeforces blog meant to say.

Yes, you are right! A node will be added “(1 + no.of children it has)” times and it is also right that the space required will be 2 * |v|(2 * |v| - 1 to be exact).

Let’s clear this!
The size says that for every vertex the array will have two indices or memory blocks. But observe that the leaf nodes have no children and their 1 space will be vacant and that space will be occupied by the parent vertex when we revisit it.

Say there is a tree rooted at 1 and has 3 children {2, 3, 4}. Now when we do the tour 1 will be added in the list every time it has a child node + one time(in the start). Children will be added only once. So the total space will be 1 + 4 + 3 = 7.

Why 7 and not 8? Because vertex 1 will be added at the start only once(remember 2 places for each vertex).