De Bruijn Sequence - Implementation

function deBruijn(n):
    if n == 1:
        return "01"

    // Build adjacency list
    // Vertex v has edges to 2*v mod 2^(n-1) and (2*v+1) mod 2^(n-1)
    numVertices = 2^(n-1)
    adj = array of lists

    for v from 0 to numVertices - 1:
        adj[v] = [2*v mod numVertices, (2*v + 1) mod numVertices]

        // Hierholzer from vertex 0
        path = hierholzer(adj, 0)

        // Build result: first (n-1) bits of start vertex, then last bit of each edge
        result = binary(path[0], n-1)
        for i from 0 to path.length - 2:
            result = result + str(path[i+1] mod 2)

            return result

This runs in $O(k^n)$ time and uses $O(k^n)$ space.