Binary Tree interal nodes+leaves proof

Question

Let us define the length of the inner path of a binary tree to be the sum of the depths of all internal nodes in the tree ,

Let us define the length of the outer path of the binary tree to be the sum of the depths of all the leaves in the tree.

I need to prove that, in a full binary tree with $n$ internal nodes and an internal path $i$ and an external path $e$, $$e = i + 2n$$

I think that induction will be a great way to prove this, but I wasn't able to prove it until now. How I can prove it?

Answer 1

First note that a full binary tree either consists of a single node, or a root with two subtrees, each of which is itself a full binary tree.

Therefore if we prove

• The theorem is true for a one-node tree
• The theorem is true for any binary tree if it is true for each of the subtrees of the root

then we will have proved it for all binary trees.

Since you are apparently not familiar with this method of proof, let me point out the parallel to induction. What we prove in induction is first that the statement is true for $1$, and second that it true for any number that we can get by starting at $1$ and counting up by ones. Since these are all the integers, we have proved the statement for all the integers. So the principle of induction says nothing more than we get all the positive integers by starting with $1$ and counting up.

Can you take it from here? Prove the basis, then suppose it's true for the left and right subtrees $L$ and $R$ of some full binary tree $T$. Relate the internal and external paths of $T$ to the internal and external paths of $L$ and $R$.