Time and Space Complexity

Time complexity: $O(V + E)$

• Checking conditions: $O(V)$ to count degrees
• Hierholzer's algorithm: $O(E)$ since each edge is processed once
• Total: $O(V + E)$

Space complexity: $O(V + E)$

• Adjacency list: $O(V + E)$
• Stack: $O(V)$ in the worst case
• Result path: $O(E)$

For dense graphs where $E = O(V^2)$, this becomes $O(V^2)$.

Hierholzer's algorithm is optimal since you must read all edges.