+14 votes
1.8k views

Which of the following statements is false?

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

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

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

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

asked
retagged | 1.8k views
+3
I think B should be connected components in place of converted components.

## 5 Answers

+11 votes
Best answer

Answer is $B$.

1. True.
2. False.
3. True.
4. True.
answered by Boss (34k points)
edited
+2
Elaborate (a) part..
0
anybody explain A part
0
explain this "Given the prefix and postfix walks over a binary tree, the binary tree cannot be uniquely constructed."
0
Without inorder we can't  construct binary tree.
0
Inorder of a bonarbtree can be obtain from sorted sequence right ? Then why option c is true.
+4 votes

Refer this link for the explanation

answered by (323 points)
+3 votes
A- An optimal binary search tree is a binary search tree for which the nodes are arranged on levels such that the tree cost is minimum.

B-B should be answer because we can find BFS only if Connected components

option B
answered by Loyal (6.9k points)
+3 votes
Answer B, We can randomly select a source vertex and run BFS algorithm, after that we need to check each vertex whether it's distance from source is still infinite or not(note: BFS algorithm first initializes each vertex's distance  from source as infinite and source's distance as 0) . If we find any vertex  having infinite distance then the graph is not connected(Assuming the graph is undirected)
answered by Active (1.8k points)
0
For directed graph Dfs is also applied in most cases ...
0
How?
+1 vote

Option B is false. We can use BFS to find connected components.

https://www.geeksforgeeks.org/connected-components-in-an-undirected-graph/

answered by Active (3.7k points)
Answer:

+16 votes
1 answer
1
+17 votes
4 answers
2
+12 votes
6 answers
3