Answer the following questions so as to justify Theorem 2.7. 

a. Draw a binary tree with height 7 and maximum number of external nodes. 

b. What is the minimum number of external nodes for a binary tree with height h? Justify your answer. 

c. What is the maximum number of external nodes for a binary tree with height h? Justify your answer. 

d. Let T be a binary tree with height h and n nodes. Show that 

e. For which values of n and h can the above lower and upper bounds on h be attained with equality?

Let T be a proper binary tree with n nodes, and let h denote the height of T. Then T has the following properties: 

1. The number of external nodes in T is at least h + 1 and at most 2^h. 

2. The number of internal nodes in T is at least h and at most 2^h − 1. 

3. The total number of nodes in T is at least 2h + 1 and at most 2^h+1 − 1. 

4. The height of T is at least log(n + 1) − 1 and at most (n − 1)/2, that is, log(n + 1) − 1 ≤ h ≤ (n − 1)/2. 

Transcribed Image Text:

log(n + 1) – 1< h < (n – 1)/2