Tree Euler Tour Order

Problem

Compute the DFS preorder of a tree rooted at root, visiting smaller-index children first, together with subtree sizes.

Return [order, sizes] where order is the node sequence of the depth-first traversal and sizes[i] is the number of nodes in the subtree rooted at i. edges is a list of [u, v] pairs.

Hint

Subtree sizes fall out of the reverse preorder accumulation.

Test cases

case 1

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

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

case 2

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

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

case 3

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

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

case 4

in: [1,[],0]

expected: [[0],[1]]

Starter codePython

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

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