0
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.