Euler Tour DFS
TraversalsEasyFlatten tree hierarchies into 1D arrays with subtree entry/exit times.
Alt+Shift+E
Configuration Panel
Adjust tree nodes and edges on the canvas then run the Euler Tour flattener.
Tree Layout Canvas
Double-click empty canvas to create root, select node to add child or delete.
Time Complexity
O(N)
Auxiliary Space Complexity
O(N) flattened array size
Conceptual Overview
An Euler Tour flattens a tree into a 1D array representation by recording the node sequence traversed during DFS. This allows mapping tree subtree operations into contiguous array range queries.
Algorithm Mechanism
Runs DFS. Appends the node key to the tour array when entering it, recursively traverses child nodes, and appends the node key again when backtracking back up. Entry tin[u] and exit tout[u] times denote subtree boundaries.
Source: CP-Algorithms reference guide