Binary Tree mathematical equation for number of internal nodes

Question

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

Answer 1

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$$

2. 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$$