In what sense is DFS faster than BFS?

Question

While reading about DFS vs BFS, I came across a statement that DFS is faster than BFS, and requires less memory.

My implementation is in C++ for both, making a stack for DFS and queue for BFS. Can someone please explain what, and how are the speed and memory requirements different?

Answer 1

• Memory requirements: The stack size is bound by the depth whereas the queue size is bound by the width. For a balanced binary tree with n nodes, that means the stack size would be log(n) but the queue size would b O(n). Note that an explicit queue might not be needed for a BFS in all cases -- for instance, in an array embedded binary tree, it should be possible to compute the next index instead.

• Speed: I don't think that's true. For a full search, both cases visit all the nodes without significant extra overhead. If the search can be aborted when a matching element is found, BFS should typically be faster if the searched element is typically higher up in the search tree because it goes level by level. DFS might be faster if the searched element is typically relatively deep and finding one of many is sufficient.