CODEWITHSUNDEEP
pythonrecursiontreebreadth-first-search
user908015
user908015

Reputation:

Breadth First Traversal for a Tree, Python

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!!

Upvotes: 4

Views: 6747

Answers (2)

luke14free
luke14free

Reputation: 2539

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

Upvotes: 8

Andrew Aylett
Andrew Aylett

Reputation: 40720

Yes, you'll have to use a queue to hold nodes which you've checked but have yet to recurse into.

Start with the root node in the queue, then repeat [pop a node and for each of its children, perform whatever action you need (res += [tree.key]) and push it on the queue].

Upvotes: 3

Related Questions