Time complexity:
- Checking conditions: to count degrees
- Hierholzer's algorithm: since each edge is processed once
- Total:
Space complexity:
- Adjacency list:
- Stack: in the worst case
- Result path:
For dense graphs where , this becomes .
Hierholzer's algorithm is optimal since you must read all edges.