ML Prep

Traverse reachable nodes with iterative DFS

Problem

Implement dfs_order(graph, start) using an explicit stack. The graph is a dictionary whose neighbor lists define the desired visit order. Return nodes in first-visit order, visiting the first listed unvisited neighbor before later neighbors. Handle cycles and neighbor-only nodes.

Reveal answer or reference solution

Pop from a LIFO stack, skip previously seen nodes, then mark and record the node. Push neighbors in reverse list order so the first listed neighbor is popped next. A set prevents revisits. The traversal is O(V+E)O(V + E).

def dfs_order(graph: dict[str, list[str]], start: str) -> list[str]:
    order: list[str] = []
    seen: set[str] = set()
    stack = [start]
    while stack:
        node = stack.pop()
        if node in seen:
            continue
        seen.add(node)
        order.append(node)
        neighbors = graph[node] if node in graph else []
        for neighbor in reversed(neighbors):
            if neighbor not in seen:
                stack.append(neighbor)
    return order

Public tests

  • dfs_order({"A": ["B", "C"], "B": ["D"], "C": [], "D": []}, "A") → ['A', 'B', 'D', 'C']
  • dfs_order({"A": ["B"], "B": ["A"]}, "A") → ['A', 'B']
  • dfs_order({}, "Q") → ['Q']
Outcome

Previous attempts

Loading attempts saved in this browser…

    Review Screening Results