GATE CSE 1994 | Question: 1.22

Question

Which of the following statements is false?

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

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

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

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

Comments

I think B should be connected components in place of converted components.

---

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. for more information click here

Answer 1

The answer is B.

• A. True.
• B. False.
• C. True.
• D. True.

Comments

@pavansan yes in case of full binary tree only we can construct tree with preorder and postorder

---

WE CAN CONSTRUCT STRICTLY BINARY  TREE USING THE PRE ORDER AND POST ORDER

---

strictly binary tree is also sometimes referred to full binary tree

Answer 2

$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 and it can be performed efficiently using Dynamic programming.click here

                          when $j\geq i $ $\bigg\{E = E[i,r-1] + E[r+1,j] + W(i,j)\bigg\} $

                            when $j\geq i $ $\Big\{W(i,j) = \Sigma^j_{l=i} p_l + \Sigma^l_{l=i-1} q_l \Big\}$

$B.$ To find Connected components we can start with either BFS or DFS but DFS is preffered over BFS because BFS takes exponential amount of memory whereas DFS takes linear amount of memory

$C.$ Using prefix and postfix the binary tree cannot be uniquely constructed check here

$D.$ It can be used and it consumes linear amount of memory 

So $B$ is right answer

Comments

BFS takes exponential amount of memory whereas DFS takes linear amount of memory

How?

---

https://cs.stackexchange.com/questions/73686/why-do-we-prefer-dfs-to-find-connected-components

Answer 3

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)

Comments

For directed graph Dfs is also applied in most cases ...

---

How?

Answer 4

https://gateoverflow.in/113167/ugcnet-dec2016-ii-25 

Refer this link for the explanation 

Answer 5

well go through every option and lets see which option is false

option a)Dynamic programming minimizes the search cost by calculating the weighted search cost for all subtrees.this makes option a is true.

option b)By BFS (or even DFS) on all unvisited nodes in an undirected graph,we can identify the connected components.so this option is false.

option c)here we need to be careful because as far as i know we can construct binary search tree with prefix and postfix but we cant construct binary tree with only prefix and postfix for this construction we need infix and with the combination of prefix or postfix.heyy..i mean i am talking in terms of order but context same so no worries.So,yeah asking binary tree and not binary search tree so this option is true.

option d)same as option b with dfs also we can find our connected components of a graph.so this option also true

so finally option b is false

I hope this helps !!🙂

 

Answer 6

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

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