Hierholzer's algorithm finds an Euler path in time.
Idea: Start from a valid vertex. Follow edges, removing them as you go. When stuck, backtrack and insert the path you found.
Core idea: When you get stuck at a vertex, all edges from that vertex are used. But you might have skipped edges earlier. Backtrack to find them.
The algorithm naturally handles this by building the path in reverse order using a stack or recursion.
Space complexity is for the data structures used.