Breadth first search is a strategy in which root node is expanded first and then all successors are expanded. It means that all the nodes at a given depth are expanded before any other node at the next depth level can be expanded. While expanding the nodes the information of the successors needs to be stored in the memory so that in the next iteration those particular nodes can be expanded.

For the given tree the BFS expansion will be :

1 2 3 4 5 6 7 8 9 10 11 12

BFS guarantees to find a path in a tree/graph except for the following conditions:

• The graph or tree is not cyclic i.e it doesn’t have a curve.
• A give child node should not have infinite successors. If this happens then the algorithm will be expanding the child node forever.
• Breadth-first search is complete. This means that if there is a solution breadth-first search will find it regardless of the kind of graph.

DFS(Dept First Search) always continue to expand the deepest node of a first successor till it reaches a leaf node. DFS needs to store only a single path from the root to a leaf node, along with remaining unexpanded sibling nodes for each node on the path. DFS doesn’t guarantee to find a shortest path , because it may happen that it has found a path by expanding the first child but there is an optimal path for some other child of a same parent.

For the given tree the DFS expansion will be:

1 2 5 9 10 6 3 7 11 12 8

Note: left node is given a priority to expand first.

DFS guarantees to find a path ina tree/graph except for the following conditions:

• The graph or tree is not cyclic i.e it doesn’t have a curve.
• A give child node should not have infinite successors. If this happens then the algorithm will be expanding the child node forever.

BFS and DFS are called uninformed search which means that it knows only the goal state and start state, to achieve or find the path it simply generates the successors only and doesn’t consider other information like at given time what is the current state, how far is the goal state and what  is the heuristic for the goal state.

Advantage of BFS over DFS is :

• BFS guarantee’s to give an optimal path for a given tree.
• BFS generally proves faster than DFS

Advantage of DFS over BFS is :

• The major advantage DFS has that it take less memory for finding a path than BFS.

	BFS	DFS
Time	O(b^(d+1))	O(b^m)
Space	O(b^(d+1))	O(bm)
Optimal	Yes	No
Complete	Yes	No