1
$\begingroup$

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.

  • 1
    If this is homework, I think you're supposed to mark it as such. As a preliminary hint, [structural induction](http://en.wikipedia.org/wiki/Structural_induction) is not mathematical induction. The second paragraph of that article might help you.2010-10-12

2 Answers 2