Proof for number of internal nodes in a tree

Question

I was reading about compressed tries and read the following:

a compressed trie is a tree which has L leaves and every internal node in the trie has at least 2 children.

Then the author wrote that a tree with L leaves such that every internal node has alteast 2 children, has atmost L-1 internal nodes. I am really confused why this is true.

Can somebody offer a inductive proof for it?

Answer 1

Inductive proof:
we will prove it by induction on L - the number of leaves in the tree.
base: a tree made out of 1 leaf is actually a tree with only a root. It has 0 internal nodes, and the claim is true.
assume the claim is true for a compressed tree with L leaves.
Step: let T be a tree with L+1 leaves. choose an arbitrary leaf, let it be l, and trim it.
In order to make the tree compressed again - you need to make l's father a leaf [if l's father has more then 2 sons including l, skip this step]. We do it by giving it the same value as l's brother, and trimming the brother.
Now you have a tree T' with L leaves.
By induction: T' has at most L-1 internal nodes.
so, T had L-1+1 = L internal nodes, and L+1 leaves, at most.
Q.E.D.

alternative proof:
a binary tree with L leaves has L-1 internal nodes (1 + 2 + 4 + ... + L/2 = L-1)
Since at "worst case" you have a binary tree [every internal node has at least 2 sons!], then you cannot have more then L-1 internal nodes!

Answer 2

You should try drawing a tree with L internal nodes, where every node has 2 children and there are L leaves. If you see why this is impossible, it won't be hard to figure out why it does work for L-1 internal nodes.

Answer 3

Ok, so I'll have a go.

Define trees for a start:

T_0 = { Leaf }

T_i = T_i-1 union { Node(c1, ..., cn) | n >= 1 && ci in T_i-1 }

Trees = sum T_i

Now, the (sketch) proof of your assertion.

1. It is easy to check it for T_0

2. For T_i: if t \in T_i it is either in T_i-1 or in the new elements. In the former case, use IH. In the latter case check the assertion (simple: if cis have L_i leaves, t has L = L_1 + ... + L_n leaves. It also hase no more than L_1 - 1 + L_2 - 1 + ... + L_n - 1 + 1 inner nodes (by IH for children, +1 for self). Because we assume each inner node has at least two children (that's the fact from the trie definition), it is no more than L_1 + l_2 + ... + L_n - 2 + 1 = L - 1).

3. By induction, if the assertion holds for t in T_i for all i, it holds for t in Trees.