search
Log In
0 votes
110 views

Which of the following search method takes less memory ?

  1.  Depth-first search
  2.  Breadth-first search
  3.  Linear search
  4.  None of the above
in Unknown Category
edited by
110 views

1 Answer

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.


edited by

Related questions

1 vote
2 answers
1
90 views
Which of the following problem cannot be solved without recursion? Tower of Hanoi Fibonacci series Tree Traversal None of the above
asked Mar 2, 2018 in Unknown Category gatecse 90 views
0 votes
1 answer
2
88 views
If there is a graph such that there is a unique path between any pair of vertices. The graph is a ________ Mesh Grid Tree Bipartite graph
asked Mar 2, 2018 in Unknown Category gatecse 88 views
0 votes
1 answer
3
105 views
Which of the following is not used for hash function? Mid-square method Division method Folding method Probe method
asked Mar 2, 2018 in Unknown Category gatecse 105 views
0 votes
2 answers
4
162 views
If the post order traversal of tree gives $ab - cd * +$, then the label of the nodes A, B, C, ......, G will be a, -, b, +, c, *, d +, -, *, a, b, c, d -, a, +, b, c, d, * a, b, c, d, -, *, +
asked Mar 2, 2018 in Unknown Category gatecse 162 views
...