Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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?

share|cite|improve this answer

How do you define a leaf? The idea of structural induction would be to show that whenever you add a new node to an existing tree, the difference between leaves and nodes without right siblings stays constant. Without the leaf definition I can't help further.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.