Question

Given the sequence of numbers: 20, 7, 34, 29, 43, 40, 8, 12, 30, 42

(a)[7 pts] Show the resulting BST after inserting the numbers as keys.

(b)[9 pts] What will be the resulting tree if you delete the root? Show the tree and explain the steps taken in deleting the root according to the delete procedure we discussed in class.

(c)[9 pts] Can you reorder the original sequence of numbers to obtain a tree of a smaller height? If, yes, show the permutation of the sequence and the new tree. If no, argue why a smaller height is not obtainable.

Answer 1

Binary Search Tree

Step 1: Insert keys 20 & 7        

Step 2: Insert key 34                           

Step 3: Insert key 29

Step 4: Insert key 43                                                                

Step 5: Insert key 40     

Step 6: Insert key 8                                                                          

Step 7: Insert key 12           

Step 8: Insert key 30                                                                         

Step 9: Insert keys 42                 

which is Required Binary Search Tree after insertion

b) Delete Root:

Here we need to find out the Least value in Right Sub Tree

Swap Least value in Right Sub Tree and Root

Now Delete 20

Which is Required Tree after deleting Root

c) To obtain a tree of a smaller height then the sequence as follows

30, 8,42,7,12,40,43,29,34

The New tree as follows