Tree Traversal - Depth First Search

dfs.py

from collections import defaultdict

def recursive_dfs(tree, node, path=[]):
    """
    Recursive depth first search
    """
    path.append(node)
    for child in tree[node]:
        path = recursive_dfs(tree, child, path)
    return path

def iterative_dfs(tree, node, path=[]):
    """
    Iterative depth first search
    """
    queue = [node]
    while queue:
        n = queue.pop(0)
        path.append(n)
        queue = tree[n] + queue
    return path

# -------------------- #
#           1          #
#         / | \        #
#        2  7  8       #
#      /  \    | \     #
#     3    6   9  12   #
#    / \       | \     #
#   4   5      10 11   #
# -------------------- #
tree = defaultdict(list, {
    1: [2, 7, 8],
    2: [3, 6],
    3: [4, 5],
    8: [9, 12],
    9: [10, 11]
})

print "recursive_dfs:", recursive_dfs(tree, 1)
# recursive_dfs:  [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]

print "iterative_dfs:", iterative_dfs(tree, 1)
# iterative_dfs:  [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]