Proof of induction on binary trees

Question

Now I am working on a problem in an algorithm design tutorial, and I hit a little brick wall.

The problem is this:

A binary tree is a root tree in which each node has at most two children. Show by induction that in any binary tree, the number of nodes with two children is exactly one less than the number of leaves.

I'm pretty sure how to do this: the base register has a single node, which means that the tree has one leaf and zero nodes with two children. However, I am not quite sure what the inductive step entails.

Answer 1

A tree with a single node without children (obviously) has / - one leaf. The number of nodes with two children (0) is exactly equal to the number of sheets (1).

Adding a node to an existing node that has no children does not change the number of nodes with two children and the number of sheets.

Adding a node to an existing node, which has one child, increases the number of nodes with two children by 1, and also increases the number of sheets by 1.

You cannot add a node to an existing node with any other number of children.

Since the number of nodes with two children begins as exactly one less than the number of leaves, and adding a node to the tree either does not change the number or increases one by one, then the difference between them will always be exactly the same.

Answer 2

With induction on the number of nodes with two children:

Base - 0 nodes with 2 children - 1 leaf (provided that the root is not considered one). Step. Let T be a tree with n + 1> 0 nodes with 2 children.

=> there is node a with 2 children a1, a2 and in the subtree, the root in a1 or a2, there are no nodes with 2 children. we can consider its subtree root in a1.

=> delete the subtree embedded in a1, we got a tree T 'with n nodes with 2 children.

=> T 'has n + 1 leaf.

=> add a subtree, root in a1 in T '- we added one leaf and one node with two children.

There are a few holes you need to make, but they work. Sorry for my bad english.