Question

Which of the following statement(s) is/are not true?
1. Optimal binary search tree construction can be performed efficiently using dynamic programming.
2. BFS cannot be used to find connected components of a graph.
3. Given the prefix and postfix walks over the binary tree, the binary tree cannot be uniquely constructed.
4. DFS can be used to find connected components of a graph.
Choose the correct answer from the options given below:

• (A) and (C) only
• (B) and (D) only
• (D) only
• (B) only

Hint:

BFS and DFS are powerful graph traversal techniques; understand their roles in finding connected components.

Answer 1

The Correct Option is D

- Statement A: True. Optimal binary search tree construction is solved using dynamic programming. - Statement B: False. BFS can indeed be used to find connected components of a graph. - Statement C: True. Given prefix and postfix traversals, a binary tree cannot be uniquely reconstructed. - Statement D: True. DFS is commonly used for finding connected components of a graph.