2k 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

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

Answer is $B$.

1. True.
2. False.
3. True.
4. True.
answered by Boss (34.1k points)
edited
+4
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."
+1
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.
0
@Chintan Patel  That will be in case of binary search tree not in binary tree
0
got it bro tq !!

Refer this link for the explanation

answered by (447 points)
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 (2.2k points)
0
For directed graph Dfs is also applied in most cases ...
0
How?
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 (7.5k points)
+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.9k points)

1
2