Show that the maximum number of vertices in a binary tree of

Show that the maximum number of vertices in a binary tree of height n is 2^n + 1 - 1.

Solution

we need to show that the maximum number of vertices in a binary tree of height n is 2ⁿ⁺¹ - 1

we will use induction to prove the given statement.

we know that binary tree is a tree each vertices has 0 or two children.

Base case : consider that height of the binary tree n is 0 so we can say that maximum number of vertices in binary tree is 2⁰⁺¹ - 1 = 2 - 1 = 1

we know that when binary tree has height it has only one vertex so the given statement is true for n=0

Induction hypothesis : Assume that maximum number of vertices in a binary trr of height n is 2ⁿ⁺¹ - 1

we need to prove the statement for n=k+1

now assume that the height of the tree is n = k+1

The root of the tree has left subtree and right subtree each with height at most k

If we remove the root vertex we have binary left subtree and binary right subtree with height k so from induction hypothesis the maximum number of vertices in each subtree is 2^k+1 - 1

Adding them togather we have maximum number of vertices is 2*(2^k+1 - 1)

now add the root of the tree we can say that maximum number of vertices of a binary tree with height k+1 is

2*(2^k+1 - 1) + 1 = 2*2^k+1 - 2 + 1 = 2^(k+1)+1 - 1

so we can say that statement is true for n = k+1

so by induction we can say that,

The maximum number of vertices in a binary tree of height n is 2ⁿ⁺¹ - 1