Euler Tour Entry and Exit

Problem

Return entry and exit times for every node of a tree rooted at root.

Run a DFS visiting children in increasing order and assign a global timer that increments on both entry and exit: tin[v] is the time v is first reached and tout[v] is the time after its whole subtree is processed. edges is a list of [u, v] pairs. Return the list of [tin, tout] pairs in node order.

Hint

tout - tin always equals twice the subtree size, because every node is entered and left once.

Test cases

case 1

in: [3,[[0,1],[1,2]],0]

expected: [[0,5],[1,4],[2,3]]

case 2

in: [4,[[0,1],[0,2],[0,3]],0]

expected: [[0,7],[1,2],[3,4],[5,6]]

case 3

in: [1,[],0]

expected: [[0,1]]

case 4

in: [5,[[0,1],[1,2],[1,3],[3,4]],0]

expected: [[0,9],[1,8],[2,3],[4,7],[5,6]]

Starter codePython

def euler_tour_entry_exit(n, edges, root):
    # Your code here
    pass

4 test cases · run your code against them in the editor