Is DFS better than BFS for space complexity when finding path from root to a node in a tree?

Question

For simplicity, and I think without loss of generality, we can consider a binary tree. Suppose that we want to find the path between the root node and some node in the tree (we don't know where it is and only that it exists in the tree).

Worst case scenario is if the node was a leaf node at the largest depth.

If we want to find the path to this node, is DFS a lot better memory wise? DFS would incur O(h) (h = height of tree) recursion space and the space used to store the current path is also O(h) (not certain of this, but I think this is right). So the space complexity is O(h) I believe.

If we used BFS, we'd end up storing like 2^h paths with each path being O(h) long. So the space complexity is O(2^h * h).

Is this analysis correct, or am I missing something here?

Answer 1

In the case of the binary tree, and assuming your binary tree is balanced, yes, I think you will be using more space at any given time in general with BFS. DFS would be allocating and releasing memory space, while BFS would be holding memory increasingly as it goes down the tree.

BFS would be simplified because you don't need really to mark visited nodes as you do with graphs, and if each node had a pointer to their parent, you wouldn't need to keep track of paths. That pointer to parent solution would also help your DFS, because it is a tree, and you can be sure that when you find the node, walking back to the root through the parent pointers is the shortest path.

If you binary tree is very unbalanced, your average case scenario could favor BFS at times because it could find the node quicker using less pointer references at any given time after all.

Answer 2

To keep it short and simple, the answer is yes.

BFS, in addition to the set of visited nodes, makes use of queue for unprocessed nodes (and at each step in the process, you enqueue the unvisited neighbors of the current node, etc.). Also, for the BFS that keeps track of the path, you've to store the pointer to the predecessor node.

Whereas DFS (which passes the set of visited nodes as a parameter to the recursive function) makes use of the recursive function to trace its path back to the source node. No additional queue is required here.

For more details, visit this question.

Answer 3

The answer to your question is it depends on the structure of the tree. Given a tree with n nodes, the worst-case space complexity for DFS is O(n). Similarly the worst-case space complexity for BFS is O(n).

DFS has O(n) space complexity because of the use of a stack (either call stack or manually managed stack). In the worst case a tree can have all nodes in a line from root to leaf giving the tree a height of n-1. And all nodes would be stored in the stack at the leaf level.

BFS has O(n) space complexity because in the worst case, the root is connected to all other nodes and BFS would create a 2-level tree with the root at level 0 and all other nodes at level 1. Hence the BFS queue would contain n-1 nodes which uses O(n) space.

To summarize for trees where height is less than max width, DFS uses less space asymptotically. For trees where max width is less than height BFS uses less space asymptotically.