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

1

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?

0

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.