3
$\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.

Improve this question
$\endgroup$
7
  • $\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
    Commented Sep 3, 2017 at 18:09
  • $\begingroup$ Related question. Also this. Duplicate? $\endgroup$
    – Raphael
    Commented Sep 3, 2017 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
    Commented Sep 3, 2017 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
    Commented Sep 3, 2017 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
    Commented Sep 3, 2017 at 22:16

1 Answer 1

Reset to default
8
$\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$?

Improve this answer
$\endgroup$
2
  • $\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
    Commented Sep 3, 2017 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
    Commented Sep 3, 2017 at 19:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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