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$.
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:
Now for the shocker:
- 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?