# Binary Tree interal nodes+leaves proof

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?

• What do you mean by an "internal path exists" and and "external path exists"? Your definitions of the length of an inner path and the length of an outer path have nothing to do with any paths; they're stated in terms of all the internal and external nodes of the tree. May 28 '19 at 10:22
• Edited , now it is better? May 28 '19 at 13:45
• Prove it by recursion ("structural induction."). Assume it's true for the left and right subtrees of the root. If you're not comfortable with this, prove it by strong induction on the height of the tree. May 28 '19 at 13:53
• Maybe you can write the structure of the proof? It will help to me a lot to understand that and to solve same proofs in the future. :). May 28 '19 at 14:26

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