is breadth first search or breadth first traversal possible without using a queue?

Question

As I remember and checked, the usual way for traversing a tree or crawling the web breadth first (BFS) is by using a queue. Is there actually a way to implement it not using a queue?

Maybe my comment is outdated but there really is way to do that. http://stackoverflow.com/a/2549825/2198656 — Herrington Darkholme, Feb 16 '14 at 11:36

score 5 · Answer 1 · answered Jun 11 '12 at 05:10

I know this question is old now, but I just wanted to answer. You can do this with arrays, linked lists (or any other linear container) and without recursion. Keep two containers, old and new, and swap old with new when you traverse all of the items in old. Very similar to the implementation with queue.

In Python it would look like:

def breadth_first(root):
    if not root:
        return
    old = []
    new = []
    old.append(root)
    while old:
        for n in old:
            process(n)  # Do something
            if n.left:
                new.append(n.left)
            if n.right:
                new.append(n.right)
        old = new
        new = []

Runtime complexity would be the same as the queue implementation, O(n).

score 2 · Accepted Answer · answered May 13 '09 at 03:30

2

You really should be using a queue, as its easier to implement. Also, a queue allows for multiple machines to work together (one queues site while another pops sites off of the queue to traverse).

The only other way I see to do this is by using recursion (much more difficult, and uses only marginally either more or less memory).

answered May 13 '09 at 03:30

AlbertoPL

11,479
5
49
73

how do you use a stack to simulate a queue? – nonopolarity Oct 11 '10 at 05:39
see http://stackoverflow.com/questions/69192/using-stack-as-queue . Essentially, you can use two stacks. – AlbertoPL Oct 12 '10 at 03:37
The link you showed implemented a queue with two stacks. But how to convert that idea into a recursive implementation of BFS? – max Oct 30 '16 at 16:30

score 0 · Answer 3 · answered May 13 '09 at 03:29

0

With recursion. But the queue is in the stack...

answered May 13 '09 at 03:29

eKek0

23,005
25
91
119

is there like a simple pseudo code some where that can implement BFS using recursion? – nonopolarity May 13 '09 at 03:44
1

I wonder about this too. How do you want to efficiently replace a queue by using the callstack? – Lucero Jun 29 '09 at 14:01

e230217 · Answer 4 · 2015-06-08T05:12:14.740

if you care about ordering, use queue. queue preserves the insertion ordering. or you can use list's implementation, say, two array lists, to alternate. But fundamentally, list preserves ordering too.

if you don't care about ordering, you can use any set implementations. sets doesn't preserve this ordering.

For example, in BFS implementation, if you don't care the ordering of nodes, you can use two sets, old and new to alternate, rather than a queue.

is breadth first search or breadth first traversal possible without using a queue?

4 Answers4