Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
1  
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

2 Answers 2

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|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|improve this answer

Your Answer

 
discard

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