hierholzer.py

def recursive_eulerian_path(adj, start_node):
    def dfs(start):
        stack = [start]
        path = []
        while stack:
            while temp_adj[stack[-1]]:
                next_node = adj[stack[-1]].pop()
                stack.append(next_node)
            path.append(stack.pop())
        return path[::-1]

    return dfs(start_node)
  

def iterative_eulerian_path(start, adj):
    stack = [start]
    path = []
    while stack:
        u = stack[-1]
        if adj[u]:                    # while current node still has edges
            stack.append(adj[u].pop()) # follow one edge
        else:
            path.append(stack.pop())   # backtrack when no edges left
    return path[::-1]