# structural induction

prove by structural induction that in any tree T, the number of leaves is 1 more than the number of nodes that have right siblings.

My proof so far:

s(n). in any tree T, the number of leaves(L) is 1 more than the number of nodes(N) that have right siblings.

s(1) for a tree of one node, there are no right siblings so n=1. The root itself is a leave so L =1. Thus L=n+1 is true, so the basis is true.

s(n+1)...Im stuck at the induction part here.

-
If this is homework, I think you're supposed to mark it as such. As a preliminary hint, structural induction is not mathematical induction. The second paragraph of that article might help you. –  Paul VanKoughnett Oct 12 '10 at 0:17

There's a lot of similar things that are called "trees" in graph theory. I interpret this question to mean full binary trees (see Wikipedia) -- that is, each non-leaf node has a "left" and a "right" descendant.

Hint: How can you modify a full binary tree with n+1 nodes to a full binary tree with n nodes? Well, you could try deleting a leaf-node, but then you will end up with a non-leaf node with only one descendant (which isn't a full binary tree). So this isn't going to work.

So how can you ensure that a full binary tree (with fewer nodes) is constructed?

-