LCA and Euler Tour Tree

general
,
1

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.

2

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

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

4

If you feel your question was answered mark it as accepted.

5

no. i don’t feel that.I was asking, why the space requirement is 2no.of vertices even when a single node was inserted more then 2 times (1+ no.of its children, to be exact) the link which you gave(which i gave in the question), there is an Euler tour array, in which node 1 has appear 4 times (it has 3 children) and it holds for other nodes too, even then the entire tour got packed in a (2 * no. of vertices long) array. SO basically my question boils down to showing sum of (1+no.of children) for all vertices = 2no.of vertices.
Though i have found the answer, would love to hear other opinio

6

Please read the first link in the question, the tour you are talking about in which each node is inserted into array two times is ETT of type 2(as in the link), it perfectly makes sense to me, i was in water when the same amount of memory was needed even when the node were inserted each time they were encountered, (please go through both the links first). Though i have found the answers, would love to hear your opinion. Cheers

7

Actually I was describing the third type of the cf blog, though I could have been a little more clear. It just makes more sense if you think it as an equivalent to the first one. If you associate each node with an edge then you can as well count the edges inserted to the ETT. The only difference is that each edge is added twice. Also note that each node is not necessarily added more than once according to my explanation.

8

Actually, i meant to say refer to the figure given. The euler tour you are talking about just inserts the edges, and we know |E| = 2 * |V|, hence the explanation. Basically, you are adding every edges in the order of their visit time.

9

Is it clear now?

1 Like
10

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).