6
$\begingroup$

Given a full binary tree, $T$ (each node is either a leaf or possesses exactly two children), with $n$ leaf nodes: $v_1,v_2,...,v_n$, and weights associated with the leaf nodes: $w_1,w_2,...,w_n$, the cost of the tree, denoted by $|T|$, is defined as: $$|T|=\sum_{i=1}^{n}w_il_i$$ Where $l_i$ is the depth of $v_i$ in $T$.

Example:
enter image description here

The cost of the above tree is:
$0.25\times 4+ 0.18\times 4+0.5\times 3+0.4\times 2+0.31\times 3+0.2\times 4+0.1\times 4+0.65\times 3+0.2\times 3=8.7$

Now, I need to prove two things. I'll start with the first.
1. Let $T$ be a full binary tree with $n$ terminal (leaf) nodes, then $T$ has $n-1$ internal nodes.

The proof for this is not too difficult. Using induction on the number of terminal nodes, I can easily prove it. The second is not so trivial, and this is where I need help. Before I'll move on to what I'm trying to prove, I'll introduce another concept.
Let's associate now weights with internal nodes: the weight of an internal node is the sum of the weights of its two children.
Example:

enter image description here

Now for the shocker:

  1. Given a full binary tree, the sum of the $n-1$ internal nodes is the cost of the tree.

This looks surprising at first, but when you rethink about it, it makes sense (the picture above demonstrates it). My problem is proving it.
I tried proving by induction, but I got stuck in the inductive step (the base case is obvious).

Any help would be greatly appreciated.

**EDIT

Let me show exactly where I'm stuck:

Base case is easy.
The first way @Yuval Filmus suggested: For the general case, since the number of leaves $n$ is bigger than $1$, then the tree can be split to two trees; the left subtree of the root, call it $T_l$ and the right subtree of the root, call it $T_r$, each has $n_l$ and $n_r$ leaves ($n_r,n_l\geq 1$ and $n_l+n_r=n$).
Now, according to the induction hypothesis, the cost of $T_l$ is the sum of the $n_l-1$ internal nodes in $T_l$, and the cost of $T_r$ is the sum of the $n_r-1$ internal nodes in $T_r$.
I don't know what exactly does that imply with regards to the entire tree $T$...

The second way @Yuval Filmus suggested:
For the general case: $T$ (with its $n$ leaves) is obtained from a smaller tree, call it $T'$, in which two leaves was removed.
According to the induction hypothesis, the cost of $T'$ is the sum of its $(n-1)-1=n-2$ internal nodes.
Again, how should I proceed? I feel like something is missing...
So suppose I say the cost of $T'$ is: $|T'|=\sum_{i=1}^{n-2}w'_i$, where $w'_i$ corresponds to an internal node. (it is denoted with apostrophe on purpose, to distinguish these weights from the $w_i$s - the weights of the terminal nodes).
Am I on the right track?

$\endgroup$
  • 1
    $\begingroup$ I suggest you keep trying. Try decomposing the root. $\endgroup$ – Yuval Filmus Nov 22 '15 at 20:28
  • $\begingroup$ To tell the truth, that was the first direction I took (actually that's how I proved 1). Since it's getting late and it's my bedtime, I'll try again tomorrow and edit my post of I'll make any progress. Toda. ;) $\endgroup$ – so.very.tired Nov 22 '15 at 20:37
  • $\begingroup$ If you look at your tree as one root and two subtrees, the two subtrees are labeled correctly. Adding the root means you'll have to add the number labeling the root but on the other hand adding a root increases the depth of each leaf... $\endgroup$ – phs Nov 23 '15 at 7:13
5
$\begingroup$

There are two basic induction patterns for (non-empty) full binary trees:

  1. A tree is either a leaf or consists of a root and two full binary subtrees.

  2. A tree is either a leaf or can be obtained from a smaller full binary tree by adding two children to a leaf.

Your first question can be proved in both ways. In both cases, the base case is clear: if a tree is a leaf then it has $n=1$ leaves and $n-1=0$ internal nodes.

According to the first way, if the tree $T$ is not a leaf then it has a root and two subtree $T_1,T_2$. By induction we know that if $T_1,T_2$ have $n_1,n_2$ leaves (respectively) then they have $n_1-1,n_2-1$ internal nodes (respectively), and together with the root, this gives $n_1+n_2-1$ internal nodes for $T$, which is exactly one less than the total number of leaves.

According to the second way, the tree $T$ is obtained from a smaller tree $T'$ by adding two children to a leaf. If $T'$ has $n'$ leaves and $n'-1$ internal nodes, then $T$ has $n'-1+2 = n'+1$ leaves and $n'-1+1 = n'$ internal nodes, exactly one less than the number of leaves.

Your other statement can also be proved in both ways. I leave you the details.

$\endgroup$
2
$\begingroup$

Personally I would not prove the second statement ("the shocker") unless I was explicitly forced to do so by my professor.

The weight in a particular leaf is added to the weight of each of the nodes on the path from the leaf to the root. This is exactly the number of times the weight is counted in the cost of the tree, the depth of the leaf.

Done.

$\endgroup$
  • $\begingroup$ As a matter of fact, I was not forced to prove it by anyone, but rather chose to. As part of my course assignment, I must give a lecture to the rest of the class. The choice what to prove and what not to prove is mine. I chose to prove it, since my presentation is not long and thorough enough to my taste. Why wouldn't you prove it? $\endgroup$ – so.very.tired Nov 26 '15 at 14:59
  • 1
    $\begingroup$ Sorry, the point is that I would prove it by my argumentation above, and not by induction. Of course, I applaud your plan to go into details like this. $\endgroup$ – Hendrik Jan Nov 27 '15 at 12:52
  • $\begingroup$ OK, I think I'll go with your argumentation above. Sounds reasonable. $\endgroup$ – so.very.tired Nov 27 '15 at 21:11

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.