Proof by induction that every non-empty tree of height h contains fewer than 2^n+1 nodes

Question

I am stuck on the induction case of a problem.

The problem:

Define the height of a tree as the maximum number of edges between the root and any leaf. We consider the height of an empty tree to be -1, and the height of a tree consisting of a single node to be 0. Prove by induction that every non-empty binary tree of height h contains fewer than 2 ^(h+1) nodes.

So I started:

Base case: h = 0 (Since a non-empty tree consists of a single node 
or 
more, the first case would be an empty node)

= 2 ⁽⁰⁺¹⁾ = 2⁽¹⁾= 2 When height is 0 the tree consists of a single, so yes 1 node is less than 2 nodes. Inductive step = h less than or greater to 0 This is where I am stuck... I know that the statement is true, since the height will always be 1 less than the number of nodes, I just don't know how to prove it algebraically.

Thanks in advance.

Think to build a h+1 tree by duplicating a h tree and adding a root node. And you should edit you question and replace 2h+1 by 2^(h+1). — Alain Merigot

Null Terminator Null Terminator · Accepted Answer · 2019-03-25T10:36:30

Suppose you have a tree with the height of n+1.

Both it's left subtree and right subtree have their height bound by n. By induction, each subtree has less than 2^(n+1) nodes, meaning at most 2^(n+1) - 1 nodes.

Since we have two subtrees, we have at most 2 * (2^(n+1) - 1 ) = 2^(n+2) - 2. Add one for the root, and the tree of height n+1 has at most 2^(n+2) - 1, which is less than 2^(n+2), as required.

Proof by induction that every non-empty tree of height h contains fewer than 2^n+1 nodes

1 Answers