Recursive BFS

bfs_recursive.py

class Node(object):
    def __init__(self, val, leftchild=None, rightchild=None):
        self.val = val
        self.left = leftchild
        self.right = rightchild

def bfs_iterative(tree, visitor):
    q = []
    q.append((tree, 0))

    curlev = 0
    while q:
        cur, lev = q.pop(0)
        if lev > curlev:
            print '-'*8
            curlev = lev
        visitor(cur)
        if cur.left:
            q.append((cur.left, lev+1))
        if cur.right:
            q.append((cur.right, lev+1))

def dumpstack(s1):
    s2 = []
    while s1:
        s2.append(s1.pop(-1))
    return s2

def bfs_iterative_stack(tree, visitor):
    s1 = []
    s2 = []
    s1.append((tree, 0))

    curlev = 0
    while s1 or s2:
        s2 = dumpstack(s1)
        cur, lev = s2.pop(0)
        if lev > curlev:
            print '-'*8
            curlev = lev
        visitor(cur)
        if cur.left:
            s2.append((cur.left, lev+1))
        if cur.right:
            s2.append((cur.right, lev+1))
        s1 = dumpstack(s2)

def bfs_recursive_helper(nodes, visitor):
    if not nodes:
        return
    next_nodes = []
    for node in nodes:
        visitor(node)
        if node.left:
            next_nodes.append(node.left)
        if node.right:
            next_nodes.append(node.right)
    print '-'*8
    bfs_recursive_helper(next_nodes, visitor)

def bfs_recursive(tree, visitor):
    bfs_recursive_helper([tree], visitor)

def printfunc(x):
    print x.val

if __name__ == '__main__':
    t = Node(1, Node(2, Node(4, Node(8), Node(9)), Node(5)), Node(3, Node(6), Node(7)))
    print '='*16
    bfs_iterative(t, printfunc)
    print '='*16
    bfs_iterative_stack(t, printfunc)
    print '='*16
    bfs_recursive(t, printfunc)