In Discrete Mathematics! Answer all of the questions.

Problem 3. A height balanced binary tree is a binary tree whose subtrees differ in height by at most one. This means that height balanced trees are as close to full binary trees as possible even when the number of vertices precludes it. In order to bring the height of a tree into balance we must consider two particular operations, left rotations, and right rotations. These are described pictorially below: Rotate Left tx tyL tvR tx tvL Here, the vertex y becomes the parent of vertex , the left child of y becomes the right child of r, and the parent of r becomes the parent of y. Similarly consider the right rotation shown below Rotate Right ty txL ty The rectangles tr, ty,tyL,tyR,tzL, trR are subtrees from the parent vertices. These subtrees may be empty, the rotations still work the same way. (a) Suppose a binary tree has 100 vertices, what is the maximum height of such a tree if it is to be height balanced? (b) Now consider the most unbalanced binary tree possible which has 100 ver- tices. That is a single line starting with vertex where is the parent of 0+1 How many rotations are necessary to height balance this tree