Question

1. Short Questions Given the following data: 30 20 s0 40 10 60 28 Which method will perform better: Binary Search or Binary Search Tree? a) Give explanation as well S pts) b) Draw a binary search tree using the following data (5 pts) (No need to show the steps) 24 60 17 40 S0 20 22 21 c) Give the In-onder, pre-order and post-order search ordering from the tree constructed in part (b) (5 pts) d) Give definition of a spanning tree of a Graph. Give at least one real life application of spanning tree (5 pts)

Answer 1

a)

b)

c)

In Preorder the order of Traversal is first we traverse Root then after traverse Left subtree and then traverse Right subtree

Preorder (Root, Left, Right) : 24 17 20 22 21 60 40 50

In Inorder the order of Traversal is first traverse Left subtree then after traverse Root and then traverse Right subtree Right

Inorder (Left, Root, Right) : 17 20 21 22 24 40 50 60

In Postorder the order of Traversal is first traverse Left subtree then after traverse Right subtree and then traverse Root

Postorder (Left, Right, Root) : 21 22 20 17 50 40 60 24

d)

Spanning Tree: Definition :
A Spanning tree of a graph is a subset of edges from a connected graph that touches all vertices in the graph which forms a tree (is connected and contains no cycles)

Apllication:

a cable TV company laying cable to a new neighborhood