CSC378: Height of a Complete Binary Tree

In the analysis of heaps, we've assumed that the height of the tree is . Here, we'll prove it.

Theorem

The height of a complete, balanced tree of nodes is .

Intuition

Proof

With trees, induction is useful. We'll use induction on the height, .

Basis

Inductive Hypothesis

Assume that the theorem is true for heights .

Inductive Step

We must prove that the inductive hypothesis is true for height .

Let . Note that the theorem is true (by the inductive hypothesis) of the subtrees of the root, since they have height .

Thus, the inductive hypothesis is true for height and, hence (by induction), true for all heights. A complete binary tree of nodes has height .