What is the Euler tour of a tree?
The Euler tour of a tree is a specific way to traverse a tree where each node is added when it is first visited. The Euler tour will produce an order in which the nodes are visited. Unique edges will be used as a way to figure out the order.
Euler Tour on a Tree:
The Euler tour is very similar to a DFS, but it also uses unique edges to determine the ordering.
Start at the root, traverse left to right, and create a variable to count. Initially, the root is at 0.
Every edge that is passed down the tree adds one to the count variable. Making the left child of the root count 1
If a leaf node is meant, it will go back to the last non-visited node, and the count will continue from the leaf node. Making the new node (leaf node count value + 1) since there is technically 1 non-visited edge
Applications of Euler Tour Ordering:
Euler Tour for Segment Trees:
Now that each node has a unique count value, the nodes can all be turned into an array. This means that a segment tree can be made from it. It is important to recognize that if the total number of nodes in a subtree is counted, then the segment tree can operate on specific subtrees. If an operation is supposed to be done on node 1’s subtree and the nodes are known in the subtree, The interval [1, n] in the subtree will represent the entire subtree.
Euler Tour for not-simple tree paths:
A small change to how the Euler tour is calculated can allow it to work on getting the sums along the path where potential edges might need to go backwards to reach the final goal.
In this case, two values are being stored. The value when it is first visited, but also the value when the node is left. Below is a visualization.
For this to work, the indexes when the node was first visited are given the positive version of their value. The indexes where the node was left are given the negative version of their value. When going along the path, when an edge is traversed down and then traversed back up later, it cancels itself.
This method can be used for more than just sums. It works on operations that have a way to undo themselves. Such as xor.