Assuming we’re implementing graphs with dictionaries.

Depth-first search – recursive

def rec_dfs(graph, start, path=[]):
    path = path + [start]

    for node in graph[start]:
        if node not in path:
            path = rec_dfs(graph, node, path)

    return path

Depth-first search – iterative

The neat thing about this implementation is that it differs from BFS only in the way the queue is extended.

def itr_dfs(graph, start):
    path = []
    q = [start]

    while q:
        node = q.pop(0)
        if node not in path:
            path.append(node)
            q = graph[node] + q

    return path

Perhaps more naturally I could use a stack, but then I have to reverse the nodes that I append if I want to discover the nodes in alphabetic order – e.g. if I append [b, c, d] to [a] then I pop ‘d’ instead of ‘b’.

def dfs_stack(graph, start):
    path = []
    stack = [start]

    while stack:
        node = stack.pop()
        if node not in path:
            path.append(node)
            stack += reversed(graph[node])

    return path

Breadth-first search

The code is the same as itr-dfs with a queue, but maintaining a FIFO order on the nodes:

def itr(graph, start):
    path = []
    q = [start]

    while q:
        node = q.pop(0)
        if node not in path:
            path.append(node)
            q = q + graph[node]

    return path

Level-order tree traversal

I use BFS with two queues, one for the current level and one for the next level. When currLevel is empty (we printed all the values), nextLevel becomes currLevel and so on until they’re both empty.

def new_level_order(t):
    currLevel = []
    nextLevel = []

    currLevel.append(t)

    while currLevel:
        for node in currLevel:
            if node:
                print node.value,
                nextLevel.append(node.left)
                nextLevel.append(node.right)

        print
        currLevel = nextLevel
        nextLevel = []

Iterative deepening depth-first search

The problem with BFS is that is has both time and space complexity of O(branching factor ^ height of the tree). There’s little we can do about time, which is linear to the size of the graph/tree – O(b^d), but we can do much better in terms of space using IDDFS. The idea is to run a DFS with limited depth repeatedly, increasing the depth limit at each iteration. The space complexity of IDDFS is O(bd), and since the cost of searching at the deepest level dominates the cost of searching up to (height – 1) the fact that IDDFS visits the same levels multiple times is actually not that bad.

def printLevelOrder(t):
    for i in range(1,4):
        printGivenLevel(t, i)
        print

def printGivenLevel(t, level):
    if not t:
        return
    if level == 1:
        print t.key,
    elif level > 1:
        printGivenLevel(t.left, level - 1)
        printGivenLevel(t.right, level - 1)