Question

Prove this Lemma.

Lemma 2.2 A binary tree with height h has at most 2h+1-1 nodes. □

Answer 1

Proof A) :

Proof by induction.

Base Case:

h = 0.

A binary tree of height 0 has one node.

2^h+1 − 1 equals one for h = 0.

Therefore true for h = 0.

Inductive Hypothesis :

Assume that the maximum number of nodes in a binary tree of height h is 2^h+1 − 1, for h = 1, 2, ..., k.

Now consider a tree T of height k + 1. The root of T has a left subtree and a right subtree each of which has height at most k. These can have at most 2 ^k+1 −1 nodes each by the induction hyptohesis. Adding the root node gives the maximum number of nodes in a binary tree of height k + 1,

2^{(2k+1 − 1)} + 1

2 ∗ 2 ^k+1 − 2 + 1

2 (^k+1)+1 − 1

Proof B) :

A complete binary tree of height h has 2^h+1 −1 nodes and (include this into the statement to prove) the bottom layer has 2 h nodes.

Base case is the same. Clearly bottom layer has 2⁰ = 1 nodes.

Given a tree of height h+1. Remove the bottom layer, leaving a complete binary tree of height h. By the inductive assumption it has 2^h+1 −1 nodes, 2^h of which are on the bottom layer. Now add the bottom layer back in.

Clearly this bottom layer has twice as many nodes as the bottom layer of the height h tree,

i.e. 2 2^h = 2^h+1 nodes and the total number of nodes is

2^h+1 −1 + 2^h+1 = 2^h+2 −1.