0. Problem

We want to visit all the nodes, starting at the root node.

visitAll(node)

1. Recursion

visitAll is the same as doing something with the current node, then visiting all the neighbors.

visitAll(node) = {
    do_something(node) # <-- do_something usually comes first in a graph traversal
    for nbr in node.neighbors:
        visitAll(nbr)
}

2. Base case

Usually, we want to stop when we hit a node that's null. But this is already built-in from our for loop over node.neighbors. If there are no neighbors we automatically stop.

3. Code

Before we code this up, there's one small problem: if there are any cycles in the graph, the above recursion will run forever. We can fix this by keeping track of of all the nodes we've already visited in a set visited_nodes, so we never run visitAll on the same node twice.

visited_nodes = set() 

def visitAll(node):
    # base case
    if node in visited_nodes:
        return

    # recursion
    do_something(node)
    visited_nodes.add(node) # mark current node as visited before visiting neighbors
    for nbr in node.neighbors:
        visitAll(nbr)

Time Complexity $O(n)$. We visit every node in the graph.

Space Complexity $O(n)$. We store all of the nodes in a set.