## Tree

Question 1 |

If all the edge weights of an undirected graph are positive, then any subset of edges that connects all the vertices and has minimum total weight is a

Hamiltonian cycle | |

grid | |

hypercube | |

tree |

Question 1 Explanation:

__MST__:

If all edge weights of an undirected graph are positive, then any subset of edges that connects all the vertices and has minimum total weight is minimum spanning tree.

Question 2 |

A heap can be used but not a balanced binary search tree | |

A balanced binary search tree can be used but not a heap | |

Both balanced binary search tree and heap can be used | |

Neither balanced binary search tree nor heap can be used |

Question 2 Explanation:

→ In heap deletion takes O(log n).

Insertion of an element takes O(n).

→ In balanced primary tree deletion takes O(log n).

Insertion also takes O(log n).

Insertion of an element takes O(n).

→ In balanced primary tree deletion takes O(log n).

Insertion also takes O(log n).

Question 3 |

The number of leaf nodes in a rooted tree of n nodes, with each node having 0 or 3 children is:

Question 3 Explanation:

Question 4 |

A weight-balanced tree is a binary tree in which for each node, the number of nodes in the left sub tree is at least half and at most twice the number of nodes in the right sub tree. The maximum possible height (number of nodes on the path from the root to the furthest leaf) of such a tree on n nodes is best described by which of the following?

Question 4 Explanation:

Number of nodes in the left subtree is atleast half and atmost the num begin right sub tree.

No. of nodes in left sub tree = 2 right sub tree

No. of nodes in left sub tree = (n-1/3)

No. of nodes in right sub tree = 2(n-1/3)

Height of the tree = log

No. of nodes in left sub tree = 2 right sub tree

No. of nodes in left sub tree = (n-1/3)

No. of nodes in right sub tree = 2(n-1/3)

Height of the tree = log

_{3/2}n
There are 4 questions to complete.