Which one of the following statements is false?

GATE · 1994 · CS · Question 1 subparts· Modified — slightly modified from the official paper; see the solution

1. A.

   Optimal binary search tree construction can be performed efficiently using dynamic programming.

2. B.

   Breadth-first search cannot be used to find connected components of a graph

3. C.

   Given the prefix and postfix walks over a binary tree, the binary tree cannot be uniquely constructed.

4. D.

   Depth-first search can be used to find connected components of a graph.

Attempted by 29 students.