2
$\begingroup$

Here is the description of a proof problem:

A complete binary tree of depth N is a binary tree in which every node on levels $0,1,2,...,N-1$ is a parent and has two children, and each node on level N is a leaf.

It's asking for proving binary tree of depth N has $2^{N+1} - 1$ nodes.

I am not really sure how to approach this proof. I tried to plug in some values in $D(N) = 2^{N+1} - 1$ just to play with the formula, I get $D(1) = 2^{1+1} - 1 = 3$, $D(2) = 2^{2+1} - 1 = 7$, $D(3) = 2^{3+1} - 1 = 15$, and so on. I still did not see how these numbers relate to the descriptions given and how I would relate these values to given facts to build a proof.

$\endgroup$
  • $\begingroup$ Your claim is true if only the tree is a perfect binary tree. A complete tree may have fewer than $2^{N+1}-1$ nodes. A perfect binary tree is a binary tree in which all interior nodes have two children and all leaves have the same depth or same level. $\endgroup$ – fade2black Sep 3 '17 at 18:09
  • $\begingroup$ Related question. Also this. Duplicate? $\endgroup$ – Raphael Sep 3 '17 at 18:11
  • $\begingroup$ @fade2black There are multiple competing definitions of "complete binary tree". Unfortunately, the definition in the question doesn't work: a path is a "complete binary tree" by this definition, since it doesn't require interior nodes to have two children. $\endgroup$ – David Richerby Sep 3 '17 at 19:01
  • 1
    $\begingroup$ @fade2black Correct: the given definition doesn't imply any specific number of nodes. As I said, a path fits the definition and has only $N$ nodes. $\endgroup$ – David Richerby Sep 3 '17 at 19:13
  • 1
    $\begingroup$ Well, it's clearly the right definition here. As for the concepts complete and full, they are not as standard as some people here seem to think, and might mean slightly different things to different people. $\endgroup$ – Yuval Filmus Sep 3 '17 at 22:16
7
$\begingroup$

Hint 1: Draw some binary trees of depth $0, 1, 2$ and $3$. Depth $0$ is only the the root.

Hint 2: Use Induction on the depth of the tree to derive a proof.

The base case is depth $n=0$. With depth $0$ we only have the root, that is, $2^{0 + 1} - 1 = 1$ nodes, so the formula is valid for $n=0$.

The next case is depth $n=0+1=1$, since the tree is full the root must have $2$ leafs. So we have $1 + 2 = 3$ nodes in total. The formula still holds since $2^{1+1} - 1 = 3$.

Can you generalize this procedure? Does this hold for all $n \geq 0$?

$\endgroup$
  • $\begingroup$ It is not clear how this proves that the complete binary tree of depth $N$ has $2^{N+1} - 1$ nodes. It may also have $2^{N+1} - 3$ or $2^{N+1} - 5$ nodes. $\endgroup$ – fade2black Sep 3 '17 at 18:21
  • $\begingroup$ @fade2black If "complete binary tree of depth $N$" isn't uniquely determined, then you need to be saying "a complete binary tree", not "the". $\endgroup$ – David Richerby Sep 3 '17 at 19:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.