# How many vertices does a complete binary tree of height D have? Please do a proof by induction.How would you solve this using induction? geometric series The total number of vertices in a...

How many vertices does a complete binary tree of height D have? Please do a proof by induction.

**How would you solve this using induction?**

** geometric series**

**The total number of vertices in a complete binary tree is and the trees of height 1 have 1 vertex, and trees of height 2 have 3 vertices.**

*print*Print*list*Cite

### 1 Answer

First, I think your definition of height not be standard. I think the tree with just a root (1 vertex) is considered to have height 0, and the tree with a root and 2 leaves (3 vertices) is considered to have height 1. I will use your definition of height, this is just an fyi.

First, by induction, we show that a complete binary tree has `2^(D-1)` leaves:

The base case:

as you point out, the height 1 tree has 1 vertex; `2^(1-1)=2^0 = 1`

Thus this is true for the base case.

Now the induction step:

Assume that a complete tree of height ` `D has `2^(D-1)` leaves, and we want to show that a complete tree of height D+1 has

`2^(D-1+1) = 2^D` leaves

In the height D tree, we had (by assumption) `2^(D-1)` leaves. Now, to each of those leaves, we give exactly two children, which become the new leaves. This gives `2*2^(D-1) = 2^D` leaves in the height D+1 tree. So the induction step is proven.

SO:

a complete binary tree of height D has `2^(D-1)` leaves.

Now, to figure out the pattern for the number of vertices in a complete tree of height D, maybe try drawing the first few. You get:

height #vertices

1 1

2 3

3 7

4 15

5 31

What you might notice is that the relationship looks like:

vertices = `2^D-1`

So that is the relationship we will try to prove by induction.

Base case:

The tree of height 1 has 1 vertex:

`1=2^1-1` so the statement is true for the base case.

Induction Step:

Assume that a tree of height D has `2^D-1` vertices. We want to use this assumption to show that a tree of height D+1 has `2^(D+1)-1` vertices.

To get from a complete tree of height D to a complete tree of height D+1, we attach 2 children to each of the leaves in the height D tree. So we take the number of vertices in a height-D tree and add to it the number of leaves in a height-(D+1) tree. This is the number of vertices in a height-(D+1) tree.

We know the number of vertices in a height-D tree is `2^D-1` (this was our induction assumption)

We know the number of leaves in a height-(D+1) tree is `2^D`

So the total number of vertices in a height-(D+1) tree is

`2^D-1+2^D = 2(2^D)-1 = 2^(D+1)-1`

So we proved the induction step.

SO: The number of vertices in a complete binary tree of height D is `2^D-1`