# Exercise regarding complete binary trees

Suppose $$T$$ is a complete binary tree with $$n$$ leaves Let $$e$$ denote the sum of the lengths of the leaves, $$i$$ denote the sum of lengths of the internal nodes. Prove that $$e=i+2(n-1)$$.

My attempt: Consider a complete binary tree. If we look at some node we can have two cases:

Case 1: only a single node

Case 2:from the node below we have a complete binary tree

If we have only a single node "tree", we get $$0=0$$. Because of Case 2, we need to show that for any binary tree $$e=i+2(n-1)$$ holds if it holds for every one of the subtrees of the root. But I do not know how to do that.

Edit: I have been thinking of partitioning a tree into its right subtree and left subtree (and its root). For better overview I will denote the sum of the lenghts of the leaves of a tree $$T$$ with $$e_T$$ from here on and the sum of the lengths of the internal nodes with $$i_T$$, $$n_T$$ is the number of leaves of $$T$$.

I got the following equations $$e_L=\frac{e_T}{2}-n_L$$ $$e_R=\frac{e_R}{2}-n_R$$ and $$e_T=e_R+E_L+2$$. and $$i_L+i_R=i_T-2$$.

How do I continue from here on?

• Draw a picture first :) Commented Jun 12 at 19:39
• @GarethMa I have already done that.
– NTc5
Commented Jun 12 at 19:40
• I have been thinking of partitioning T into a left and right part, but I don't know what to do exactly.
– NTc5
Commented Jun 12 at 19:40
• @NTc5 you have the right idea, use the left and right part. You can see the pattern already when $n=2$ where both subtrees are leaves. Start there and extend to the case when $n=4$, then generalize to $n$. Commented Jun 12 at 23:37

Here's a picture so that it's easier for me to explain. The natural way (without just bruteforcing) is by induction. Below I denote $$e_h, i_h, n_h$$ for the $$e, i, n$$ values of a height-$$h$$ complete binary tree.

Suppose that $$e_h = i_h + 2(n_h - 1)$$. We want to relate $$e_{h + 1}$$, $$i_{h + 1}$$ and $$n_{h + 1}$$, to each other and to their $$n$$ (subtree) counterpart. Let's do them one by one.

Let's get the easiest one out of the way. $$n_h = 2^h$$ is standard - look at the top $$3$$ layers and it should be obvious.

Next, $$e_{h + 1}$$ is the sum of length of the leaves at the bottom. We want to relate this to $$e_h$$, so we look at the subtrees. Looking at the left black subtree, its structure is basically like the complete binary tree of height $$h$$, but since it's rooted at $$\color{blue}{L}$$ and not the root, each leaf's length is actually increased by one. Since there are two subtrees, $$e_{h + 1} = 2(e_h + \#\text{number of leaves in } T_h) = 2(e_h + n_h)$$.

Finally, $$i_{h + 1}$$ is the sum of lengths of internal nodes. By the same argument, $$i_{h + 1} = 2(i_h + \#\text{number of internal nodes in } T_h)$$. It is again a standard fact that there are $$2^{h + 1} - 1$$ vertices in $$T_h$$, and we have to subtract the leaves (not internal), so $$i_{h + 1} = 2(i_h + (2^{h + 1} - 1 - 2^h)) = 2(i_h + 2^h - 1)$$.

Hence, $$e_{h + 1} = 2({\color{red}{e_h}} + 2^h) = 2({\color{red}{i_h + 2(2^h - 1)}} + 2^h) = 2i_h + 6 \cdot 2^h - 4$$, while $${\color{red}{i_{h + 1}}} + 2(n_{h + 1} - 1) = {\color{red}{2(i_h + 2^h - 1)}} + 2(n_{h + 1} - 1) = 2i_h + 6 \cdot 2^h - 4$$, so both sides are equal.

• Thank you very much!
– NTc5
Commented Jun 14 at 12:12