Questions for tree

(a) Draw a maximally balanced binary search tree that can be produced from the elements: 1,2,3,4,5,6,7,8,9. Hint: a maximally balanced binary search tree minimises the average depth of its elements [3 marks] (b) Derive a recurrence for the number of degenerate binary search trees that can be generated from a given sequence of n distinct elements Recall that degenerate binary search tree contains no branches and thus is structurally similar to a linked list. You must make an argument to justify each component of your recur- rence. Remember that all recurrences have base cases so do not forget to include a base case. [6 marks] (c) Derive a recurrence for the number of different binary search tree shapes that can be derived from a sequence of n distinct values. You must carefully explain your derivation in order to get full marks for this question. Again, you must remember to include at least one base case in your recurrence [6 marks] d) Draw a sequence of diagrams showing the insertion of the values: [1,9,8,7,2,3,6, 4, 5] into an empty AVL tree, in the order shown above You must: . Show the resulting tree immediately after each insertion step (that is before any balancing has taken place). . Indicate the node(s) at which each rotation is performed . Where there is a double rotation, show the tree after each single rotation. . Show the resulting tree after balancing operation(s). [10 marks]