Page 206 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Unit 10: Heaps

of height two. Similarly, the left subtree of node 2 is a perfect binary tree of height two; and the Notes
right subtree is a complete binary tree of height two.
Figure 10.1: A Complete Binary Tree

Does there exist an complete binary with exactly n nodes for every integer n>0? The following
theorem addresses this question indirectly by defining the relationship between the height of a

complete tree and the number of nodes it contains.

Task Discuss how complete and perfect trees are closely related.

Theorem-10.1

h
h+1
A complete binary tree of height h ≥ 0 contains at least 2 and at most 2 – 1 nodes.
extbfProof First, you prove the lower bound by induction. Let m be the minimum number of
h
nodes in a complete binary tree of height h. To prove the lower bound you must show that
h
m = 2 .
h
Base Case There is exactly one node in a tree of height zero. Therefore, m = 1 = 2 .
0
0
Inductive Hypothesis Assume that m = 2 for h = 0, 1, 2, ..., k, for some k ≥ 0. Consider the
h
h
complete binary tree of height k+1 which has the smallest number of nodes. Its left subtree is a
complete tree of height k having the smallest number of nodes and its right subtree is a perfect
tree of height k-1.
From the inductive hypothesis, there are 2 nodes in the left subtree and there are exactly
k
2 (k–1)+1 – 1 nodes in the perfect right subtree. Thus,
m = 1 + 2 + 2 (k–1)+1 – 1
k
k + 1
= 2 k+1
Therefore, by induction m = 2 for all h ≥ 0, which proves the lower bound.
h
h
Next, I prove the upper bound by induction. Let M be the maximum number of nodes in a
h
complete binary tree of height h. To prove the upper bound I must show that M = 2 – 1.
h+1
h
Base Case There is exactly one node in a tree of height zero. Therefore, M = 1 = 2 – 1.
1
0
Inductive Hypothesis Assume that M = 2 – 1 for h = 0, 1, 2,..., k, for some k ≥ 0. Consider
h+1
h
the complete binary tree of height k+1 which has the largest number of nodes. Its left subtree
is a perfect tree of height k and its right subtree is a complete tree of height k having the largest
number of nodes.
LOVELY PROFESSIONAL UNIVERSITY 201