Algorithm Question:

Please do not write a real program.

The answer should be an explaination of your algorithm or pseudocode. Try to answer clearly and concisely. Thank you very much.

Question:

A node v is a lonely child if it parent has a single child. Namely, v is a lonely child if v is the unique child of its parent.

(a) Show that in an AVL tree the number of lonely children is at most n/2.

(b) True of False: If the number of lonely children in an AVL tree is c n for some constant c < 1 then the height of the tree is O(log n)? Explain your answer.