Recursive DFS into Iterative DFS with global state

Question

Here is this graph algorithm that finds a path between two nodes in a DAG.

from typing import *
def find_path(graph: List[List[int]], start: int, end: int) -> List[int]:
    path = []
    def dfs(node):
        path.append(node)
        if node == end: return True
        for neighbor in graph[node]:
            if dfs(neighbor): return True
            path.pop()
        return False

    dfs(start)
    return path

I was wondering if this code could be turned into an iterative DFS.

Here is a sample input:

graph = [[1,2],[3],[3],[]]
start = 0
end = 3
find_path(graph, start, end)

Answer 1

You could stack the node together with an iterator object that iterates its neighbors. Since your original code does not use visited flags (to avoid revisiting the same node), I will not use them here either:

def find_path(graph: List[List[int]], start: int, end: int) -> List[int]:
    stack = [[start, iter(graph[start])]]
    while stack:
        neighbor = next(stack[-1][1], None)
        if neighbor:
            stack.append([neighbor, iter(graph[neighbor])])
            if neighbor == end:
                return [node for node, _ in stack]
        else:
            stack.pop()