0
$\begingroup$

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?

$\endgroup$
4
  • 1
    $\begingroup$ 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. $\endgroup$
    – saulspatz
    May 28 '19 at 10:22
  • $\begingroup$ Edited , now it is better? $\endgroup$ May 28 '19 at 13:45
  • 1
    $\begingroup$ 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. $\endgroup$
    – saulspatz
    May 28 '19 at 13:53
  • 1
    $\begingroup$ 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. :). $\endgroup$ May 28 '19 at 14:26
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.