Question

Choose the incorrect statement about DFS and BFS from the following?

(a) BFS is equivalent to level order traversal in trees

(b) DFS is equivalent to post order traversal in trees

(c) DFS and BFS code has the same time complexity

(d) BFS is implemented using queue

This question was posed to me in final exam.

Query is from Non-recursive Depth First Search in chapter Graph Search of Data Structures & Algorithms II

Answer 1

The correct answer is (b) DFS is equivalent to post order traversal in trees

The best I can explain: DFS is equivalent to pre order traversal in trees, not post order traversal. It is so because in DFS we keep on exploring as far as possible along each branch before backtracking. So it should be equivalent to pre order traversal.