Please any one write the ans to this question,,,,
Q) Suppose one modifies the definition of an AVL tree in the following manner: The balance condition becomes |height(L(x)) &#8722; height(R(x))| <= 2, for each node x of the tree, i.e., the heights of the left and right subtrees have to differ by at most 2 (rather than at most 1, as
in the standard definition). Working with this modified definition:
(a) Draw one legal AVL tree and one illegal AVL tree.
(b) If n(h) is the smallest number of nodes in an AVL tree of height h, write a recurrence defining n(h).
(c) From the above recurrence, deduce that n(h)>= c raisedto h for an appropriate constant c > 1.
(d) Explain how the fact that n(h) is at least exponential in h implies that the balance condition given above forces the tree to be “balanced,” i.e., to have height O(log n), if n is the number of nodes in the tree.