Construct adjacency lists for each node and a map from nodes to the first entries of the adjacency lists :
* For each edge in the list, do in parallel:
** If the previous edge has x ≠ u, i.e. starts from a different node, set first =
** Else ifx = u, i.e. starts from the same node, set next =
Construct an edge list in Euler tour order by setting pointers succ for all edges in parallel according to the following rule: The resulting list succ will be circular. The overall construction takes work W = O if the tree has n nodes, as in trees the number of edges is one less than the number of nodes.
Roots, advance and retreat edges
If the tree has a root, we can split the circular listsucc at that root. In that case, we can speak of advance and retreat edges: given a pair of nodes u,v, the first occurrence of either or in the ETR is called the advance edge, and the second occurrence is called the retreat edge. This appeals to the intuition that the first time such an edge is traversed the distance to the root is increased, while the second time the distance decreases. Rerooting the tree can be done in constant time O by splitting the circular list succ at the new root.
Applications
All of the following problems can be solved in O :
Classifying advance and retreat edges: Do list ranking on the ETR and save the result in a two-dimensional arrayA. Then is an advance edge iff A < A, and a retreat edge otherwise.
Determine the level of each node: Do a prefix sum on the ETR, where every advance edge counts as 1, and every retreat edge counts as −1. Then the value at the advance edge is the level of v.
Number of nodes in a subtree rooted at v: determine advance edge, and the retreat edge in parallel, and then count the number of advance edges between and using prefix sum.
The depth-first search index of a node v: count the number of advance edges up to and including.
Henzinger and King suggest to represent a given tree by keeping its Euler tour in a balanced binary search tree, keyed by the index in the tour. So for example, the unbalanced tree in the example above, having 7 nodes, will be represented by a balanced binary tree with 14 nodes, one for each time each node appears on the tour. We can represent a forest using a collection of ET trees - one ET tree for one forest tree. This representation allows us to quickly answer the question "what is the root of node v?" by just moving to the first node of the ET tree. When the represented forest is updated, the corresponding Euler-tour structure can be updated in time O. Link/cut trees have similar performance guarantees. While LC trees are good for maintaining aggregates on paths of a tree, ET trees are better at keeping aggregate information on subtrees.
