Euler Tour Construction

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 $2n - 1$ (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.