0
$\begingroup$

I was wondering how does this equation:

$$\frac n2 + \frac n4 + \frac n8 + \dots + 1$$

go to:

$$1 + 2 + 4 + \dots + \frac n2$$

and then to:

$$\sum_{i=0}^{h-1} 2^i,\; \text{where $h$ is the height of the tree}$$

and then the result of: $n-1$

Regards

Tree example

$\endgroup$
  • $\begingroup$ A little more context will certainly help $\endgroup$ – caverac Dec 2 '18 at 11:49
  • $\begingroup$ Sure, let me add some context, sorry about that. In the first equation we can see that each level of the binary tree we are taking 1/2 of the results, First choice from root is n/2, then we split that into 1/2's again, we get n/4, etc. If we add them all up we will get the number of internal nodes, where n is the total number of leaf nodes, for example 8. If there are 8 leaf nodes, that means the tree is of height 3. If thats the case then n-1 which is 8-1 = 7, so there are 7 internal nodes of the tree. I am just stumped how to convert the equations between each other. I added an image $\endgroup$ – fynx Dec 2 '18 at 12:08
0
$\begingroup$

Having seen this question two times I'm still not sure what exactly it is about. I suppose that the question is something like this: "Given a full binary tree, how do we calculate the number of internal nodes in it?".

Assume that the height is h and the number of leaf nodes is n. Then the next level will have n/2 nodes, next level - n/4 until at the root there is just one node. This gives us the formula:

$$\frac n2 + \frac n4 + \frac n8 + \dots + 1$$

The next formula is the same with all the summands written in the reverse order. To make it more clear let's write 3 terms from both ends in both formulas

$$\frac n2 + \frac n4 + \frac n8 + \dots + 4 + 2 + 1$$

$$1 + 2 + 4 + \dots + \frac n8 + \frac n4 + \frac n2$$

The other way to see this formula is to start counting from the root. There is 1 root, then there are 2 children on the 2-nd level, then there are 4 children at the 3-rd level and so on until the last internal level of n/2 nodes. And this logic is exactly what gives us the formula of

$$\sum_{i=0}^{h-1} 2^i,\; \text{where $h$ is the height of the tree}$$

The fact that such a sum is equal to 2^h - 1 is easy to prove by induction. And 2^h is the same as n. So this give us n-1.

Another simple way to see that the number of internal nodes in a tree with n leaves is to consider it as a tree representation of knock-out tournament: each leaf is a team and each internal node represents a winner of a match between the two "incoming" nodes. See it like this it is clear that in each "match" one of the teams is eliminated and the other goes on. So if we start with n teams and at the end have just 1 "champion", it means that n - 1 teams got eliminated so there were n - 1 "matches" i.e. n - 1 internal nodes. (Note: unlike the rest of the answer, this argument works for every tree, not just full binary trees).


Update (proof that sum(2^i) = 2^n-1)

Proof by induction works like this:

  1. Base case h = 0:

$$\sum_{i=0}^{0} 2^i = 1 = 2 - 1 = 2^1 - 1$$

  1. Now assume we know that for some h that

$$\sum_{i=0}^{h-1} 2^i = 2^h - 1$$

and we want to prove that for h+1 it holds as well that:

$$\sum_{i=0}^{h} 2^i = 2^{h+1} - 1$$

It's actually very easy to prove, just take the last term from the new sum and substitute the old sum with the known proposition:

$$\sum_{i=0}^{h} 2^i = \sum_{i=0}^{h-1} 2^i + 2^h = (2^h - 1) + 2^h = 2*2^h-1 = 2^{h+1} - 1$$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you for your response. can you explain this part "The fact that such a sum is equal to 2^h - 1 is easy to prove by induction. And 2^h is the same as n. So this give us n-1." How can it be proven by induction? Regards $\endgroup$ – fynx Dec 3 '18 at 16:07
  • $\begingroup$ @fynx, see my update. I hope it clarifies that part to you. $\endgroup$ – SergGr Dec 3 '18 at 17:40
  • $\begingroup$ Thx for the prrof by induction. Yes i can follow it now. I believe you meant in step 1 that the base case should = 1 correct? We prove fr base case = 1, then assume for h, the prove for h+1. One last item, how did you get from (2^h−1)+2^h to = 2∗2^h−1? ( last line of the proof ) $\endgroup$ – fynx Dec 3 '18 at 19:08
  • $\begingroup$ @fynx, yes, top index should be 0 so h = 1. As for the other part it is just re-grouping of the terms (2^h−1)+2^h = 2^h+2^h−1 = 2*(2^h) - 1 = 2^(h+1)-1 $\endgroup$ – SergGr Dec 3 '18 at 19:24

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