Breadth First Traversal for a Tree, Python

Question

I figured out Depth First Traversal for a Tree.

def _dfs(tree, res):
    if tree:
        res += [tree.key]
        _dfs(tree.left, res)
        _dfs(tree.right, res)
    return res

I can't seem to find a solution for Breadth First Search. Will one have to use queues or stacks?

Thanks!!

Answer 1

You can go with deques. This is a classic implementation of the bfs from Magnus Lie Hetland (using a FIFO queue).

from collections import deque

def bfs(G, s):
    P, Q = {s: None}, deque([s]) 
    while Q:
        u = Q.popleft() 
        for v in G[u]:
            if v in P: continue 
            P[v] = u 
            Q.append(v)
    return P