Question

Prove that for any non -empty binary tree t if n0 be number of leaves and n1 be the number of nodes of degree 2 then n0=n1+1

Answer 1

Answer:

e number of leaves and n1

Step-by-step explanation:

tree t if n0 be number of leaves

Answer 2

Step-by-step explanation:

Let n0n0be the total number of leaves in our binary tree and n2n2 be the total number of two-children nodes. We claim n0=n2+1n0=n2+1 and will show this via induction on n2.n2.

Base Case: n2=0n2=0:

It’s pretty clear that when we have zero two-children nodes the number of leaves we can have is restricted to one. A more formal approach would be to do a proof by contradiction; first, take any two of the leaves, then work your way from the bottom to the top of the tree to find a common ancestor between them; the common ancestor would be a two-child node and would contradict the fact that we have zero two-child nodes to begin with.

General Case: n2=kn2=k, where k>0k>0

Assume via induction that we have for any binary tree with k−1k−1 two-children nodes that it has kkleaves. We need to show that if it has kk two-children nodes, it has k+1k+1 leaves. Now we can “insert” a new two-child node in three ways:

Make a leaf in the old tree have two children.

Make a one-child node in the old tree have two children.

Insert a (completely new) two-child node parent of an existing node.

For 1., we see pictorially that inserting two children into an existing leaf creates two new children nodes into the tree; these children become leaves because they will not have any children nodes themselves. In this case, we add a net of 1 leaf, as the original leaf becomes a two-children node and its two children are two new leaves.

For 2., we have that the one-child node that is promoted into a two-children node adds a net of one leaf; this is due to the fact that the newly added child is a leaf.

For 3., adding a completely new two-child node parent of an existing node will produces exactly one more leaf. One of the children of this new two-child node is the existing one, so it doesn’t add a new leaf. However, the second child of the new two-child node parent is a new leaf, similar to 2.

In all three situations, we end up adding exactly one new leaf, and because there were kkto begin with, there are now k+1k+1in total.

From the base case and general case, we conclude by induction that n0=n2+1n0=n2+1 .