0

I am reading BFS and DFS and I understood that BFS uses a queue to store the nodes while DFS uses a stack to store the nodes that are yet to be visited. But when going through the differences, I found that lot of web sites mentioned that Breadth First Search needs more memory as it needs queue to store the nodes. I did't understand why BFS only needs more memory because even DFS is using stack to maintain the nodes. Can any one please let me know if I am missing any thing?

kadina
  • 5,042
  • 4
  • 42
  • 83

2 Answers2

4

Well, for a start, balanced trees tend to be wider than they are taller. That's because every time you add a depth level to a balanced tree, you roughly double its capacity.

So, for storing 16,383 items, your width at the bottom of the tree is 8,192 but your depth is only 14:

Level  1: 1
       2: 2-3         
       3: 4-7
       4: 8-15
       5: 16-31
       6: 32-63
       7: 64-127
       8: 128-255
       9: 256-511
      10: 512-1023
      11: 1024-2047
      12: 2048-4095
      13: 4096-8191
      14: 8192-16383
paxdiablo
  • 854,327
  • 234
  • 1,573
  • 1,953
1

The main difference between BFS and DFS storage is that BFS keeps the queue of nodes it is going to visit, while the DFS stack keeps nodes it visited while going from the root to the current node (it will go back to those nodes when it finishes traversing the children of the current node).

In the worst case both BFS and DFS will store O(N) nodes in the queue or stack.

The worst case for DFS in terms of memory usage is when it stores almost all the nodes of the tree in the stack, that's when a tree looks like a linked list (each node except the last one has exactly one child). It will have N-1 nodes in the stack in this case.

For BFS the worst case in terms of memory usage would be when your root node is connected to each of the other nodes, in this case it will store N-1 nodes in the queue — just the same amount as DFS stores in the stack in its worst case.

But if we think about balanced trees (the average case), DFS will only store the path from the root to the current node each time (that's about log N nodes), while BFS will store the queue which, for balanced binary trees, can be as large as N/2 when you get to the bottom of the tree.

afenster
  • 3,468
  • 19
  • 26
  • Isn't it the case that BFS and DFS are only equal when the tree is a linked list (each node has only one branch)? For all other cases DFS uses less memory. – slebetman Sep 22 '14 at 05:55
  • For a linked list BFS will not use the same amount of memory as DFS. The DFS stack will contain all the nodes except one when it reaches the last node, while the BFS queue will contain only one node each time. – afenster Sep 22 '14 at 05:56
  • Ah OK. I was thinking of algorithms that need to build the result by concatenating values of function calls. But that by definition is DFS. – slebetman Sep 22 '14 at 06:00
  • To be clear, in the case where the tree is really just a linked list, the DFS "stack" contains every node only if DFS is implemented recursively (and without optimisation for tail recursion); if you write it with a loop and an explicit stack, nodes are popped from the stack before their neighbours are pushed, so the stack will have O(1) size for the case of a linked list, just as BFS does. The worst case for non-recursive DFS is then a tree where each internal node has two children, the second of which is a leaf; this graph has O(n) leaves, and at some point, the stack will contain them all. – kaya3 May 29 '22 at 13:48