A node in a binary tree is a called a single child, if it has no siblings (Its parent has only one child). Consider a single node ratio on a tree T.

SC(T) = (The number of single child nodes in T ) / (The number of nodes in T )

. 1. Compute the ratio SC on a binary search tree that has a cost O(n) for searching.

2. Prove that for an AVL tree T, the ratio SC(T) 1/2 .

3. Is it true that if a binary tree T has SC(T) 1/2 , then its height is O(lg n