Question

Give a proof by induction that the number of nodes of a full binary tree with a height of "h" is: (2^(h+1))-1.

Answer 1

Answer : Given data

* The number of nodes of a full binary tree with a height of "h" is: (2^(h+1))-1.

* Base Case: h = 0. As above, a tree of height 0 has exactly one node, and 2^(0+1) - 1 = 2^1 - 1 = 2 - 1 = 1, so the base case satisfies the Induction Hypothesis. Induction Hypothesis: * Spose that the result holds for some k >= 0; i.e., a binary    search tree of height k has at most 2^(k+1) - 1 nodes. 
 * Induction Step: Let T be a binary tree of height k+1. By definition of leaf, all the nodes at depth k+1 are leaf nodes.    * As we know there are at most 2^(k+1) leaves. If we remove all the leaves, we are left with a tree of height k. 
* Thus the total number of nodes in T is at most 2^(k+1) [for the leaves] + 2^(k+1) - 1 [for the remaining tree of height k, by the I.H.] = 2*(2^(k+1)) - 1 = 2^(k+1+1) - 1.
*  Hence the hypothesis holds for k+1, and so the theorem is proved.

_____________THE END______________