0 votes

Which of the following search method takes less memory ?

- Depth-first search
- Breadth-first search
- Linear search
- None of the above

0 votes

**DFS or Depth-First Search takes less memory** than BFS and Linear Search.

BFS uses a queue, which contains nodes at the front of the search. So at most all nodes at distance *d*.

whereas, DFS uses a stack, which contains nodes from root to the node being searched. So at most the radius of the graph.

If we consider a balanced k-ary tree and the depth of the tree is $O(log(n))$ and at the lowest level there are $O(n)$ nodes , then

**DFS uses $O(log(n))$ memory while BFS uses $O(n)$ memory.**