# Proving the Number of Leaves is One More Than Internal Nodes in Binary Trees

• Jairo Rojas
In summary, the proposition states that all binary trees with n leaves have n-1 internal nodes. The base case is trivial, and you have covered that above. For the induction step, you need to prove that, if P(n) is true for all n in 1,...,m, then P(m+1) is also true. This involves a similar approach to what you have above, except that you need to work backwards from a tree with m+1 leaves to one with m leaves, rather than forwards as you did above. If you can prove that induction step then, by the principle of induction, it is proven that P(n) is true for all natural numbers n.
Jairo Rojas

## Homework Statement

In a binary tree all nodes are either internal or they are leaves. In our definition, internal nodes always have two children and leaves have zero children. Prove that for such trees, the number of leaves is always one more than the number of internal nodes.

## The Attempt at a Solution

Proof by induction

Base case:
n=1
Number of leafs=1
External nodes=0

Induction step: Assume a binary tree has k internal nodes and k+1 leaves. Therefore we have to show that a binary tree with k+1 internal nodes will have (k+1)+1 leaves

If we want to increase the number of external nodes by 1 in this binary tree, we would have to make a leaf an internal node and we do this by sticking two new leaves to an old leaf. Doing this the net change in leaves is 1 because we eliminate 1 and add 2 new. So the number of external nodes is k+1 and the number of leaves is (k+1)+1. Consequently, by induction, the number of leaves is always one more than the number of internal nodes in a binary tree.

Is that correct?

Jairo Rojas said:
Is that correct?
That's certainly the idea of the induction proof. But that's too informal a way to write it, unless you have a very easygoing lecturer. A more formal approach would be as follows:

Start with a proposition P(n) which states that all binary trees with n leaves have n-1 internal nodes.
The base case is P(1), which is trivial, and you have covered that above.
For the induction step, you need to prove that, if P(n) is true for all n in 1,...,m, then P(m+1) is also true.

This involves a similar approach to what you have above, except that you need to work backwards from a tree with m+1 leaves to one with m leaves, rather than forwards as you did above.

If you can prove that induction step then, by the principle of induction, it is proven that P(n) is true for all natural numbers n.

See how you go.

## 1. What is a binary tree?

A binary tree is a data structure used to store data in a hierarchical manner. It consists of nodes, each of which can have up to two child nodes. The topmost node is called the root node, and every other node is either a left child or a right child of its parent node.

## 2. How do you count the number of leaves in a binary tree?

To count the number of leaves in a binary tree, you can use a recursive function that checks if a node has any child nodes. If it does not have any child nodes, it is considered a leaf node. You can then increment a counter variable every time a leaf node is encountered.

## 3. What are internal nodes in a binary tree?

Internal nodes in a binary tree are the nodes that have at least one child node. They are not the leaf nodes, which do not have any child nodes. Internal nodes are also known as non-leaf nodes or branch nodes.

## 4. How do you prove that the number of leaves is one more than internal nodes in binary trees?

This can be proved using mathematical induction. The base case would be a binary tree with only one node, where the number of leaves is one and the number of internal nodes is zero. For the inductive step, assume that the statement holds true for a binary tree with n internal nodes. Then, adding a new leaf node to the tree would result in n+1 internal nodes and n+2 leaves, which satisfies the statement.

## 5. What is the significance of proving the number of leaves is one more than internal nodes in binary trees?

This proof is important as it helps us better understand the structure and properties of binary trees. It also allows us to make accurate calculations and predictions in algorithms that involve binary trees, such as binary search trees and binary heaps.

• Engineering and Comp Sci Homework Help
Replies
6
Views
2K
• Set Theory, Logic, Probability, Statistics
Replies
6
Views
1K
• Engineering and Comp Sci Homework Help
Replies
1
Views
2K
• Engineering and Comp Sci Homework Help
Replies
15
Views
2K
• Engineering and Comp Sci Homework Help
Replies
5
Views
2K
• Engineering and Comp Sci Homework Help
Replies
13
Views
2K
• Engineering and Comp Sci Homework Help
Replies
5
Views
2K
• Engineering and Comp Sci Homework Help
Replies
9
Views
3K
• Engineering and Comp Sci Homework Help
Replies
1
Views
3K
• Engineering and Comp Sci Homework Help
Replies
1
Views
2K