Exercise regarding complete binary trees

Question

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?

Answer 1

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.