python

Prove proposition 8.8 part 3 on page 315. [HINT: Use induction on the height h]

Proposition 8.8 below

Let T be a nonempty binary tree, and let n, nE, nI and h denote the number of nodes, number of external nodes, number of internal nodes, and height of T, respectively. Then T has the following properties:

1. h + 1 <= n <= 2^(h+1) -1

2. 1 <= nE <= 2^h

3. h <= nI <= 2^(h) -1

4. log(n+1)-1 <= h <= n-1