function eulerTour(root):
euler = empty list
depth = empty list
first = array of size n, filled with -1 // first occurrence
function dfs(node, d, parent):
first[node] = euler.length
euler.append(node)
depth.append(d)
for child in adj[node]:
if child != parent:
dfs(child, d + 1, node)
euler.append(node)
depth.append(d)
dfs(root, 0, -1)
return euler, depth, first
Tour length is (we enter each node once and return after each child).
Build Sparse Table on the depth array. Query returns the index of minimum depth; use euler array to get the actual node.