1
$\begingroup$

A full node is a node with two children. Prove that the number of full nodes plus one is equal to the number of leaves in a nonempty binary tree.

I am not sure of how to prove this, but I have included my best attempt below:

Theorem. The number of full nodes plus one is equal to the number of leaves in a nonempty binary tree.

Proof. We use proof by induction. $\forall k \in \mathbb{N}$ let $P(k)$ be the proposition that a binary tree with $k$ nodes has $n$ full nodes and $n + 1$ leaves.

Base cases:

Let $k = 1$, then, $P(1) = 0 + 1 = 1$

A binary tree with only $1$ node has $0$ full nodes and $1$ leaf (the node itself is the leaf), so $P(1)$ is true.

Inductive Step: $\forall k \in \mathbb{N}$, we must show that $P(k)\Rightarrow P(k+1)$

We assume $P(k)$ is true for purposes of induction, and we must show that $P(k + 1)$ is true. We have two cases:

Case 1:

If we add a node to an existing leaf, then both, the number of full nodes in the binary tree and the number of leaves in the binary tree do not change.

Case 2:

Enlarging a binary tree by adding a node to an existing node that has $1$ child, makes an initial binary tree with $n$ full nodes now have $n + 1$ full nodes. Since, the parent node becomes a full node, then the number of leaves in the binary tree increases by $1$. So, the number of leaves in the binary tree becomes $(n + 1) + 1 = n + 2$

Thus, the number of full nodes we start with is exactly one less than the number of leaves, and adding a node to the binary tree either changes neither number, or increases both by exactly one, so the difference between the number of full nodes, and the number of leaves will always be $1$. So, $P(k + 1)$ is true.

Since $P(k + 1)$ is true, we can conclude that $P(k)\Rightarrow P(k+1)$ is true.

Therefore, the number of full nodes plus one is equal to the number of leaves in a nonempty binary tree.

Q.E.D

$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

This is correct, though in case 2 you basically repeat the same thing three times. Certainly the first paragraph isn't necessary, and the things you say in the third that are new can be reduced to a single equation ($(n+2)-(n+1)=1$) and tacked on to the end of the second paragraph.

$\endgroup$
3
  • $\begingroup$ First off, thank you for taking the time to review my proof. I deleted the first paragraph in case $2$. I was able to see how it was basically the same exact argument that I use in the second paragraph of case $2$. In regards to the third paragraph: I am new to proof writing, so I prefer to write everything out just to make sure that the argument I formulated in my head is the exact argument I end up writing down. With that being said, is it ok to leave the 3rd paragraph as is, or would it make my proof incorrect? Perhaps I can just tack on that equation you wrote up to the end of it? $\endgroup$
    – Cherry_Developer
    Mar 21, 2017 at 17:35
  • $\begingroup$ @Cherry_Developer it's not so much logical wrong, as a little confusing to read. I would write the case like this (your words in the first paragraph fill out the ellipsis): "Enlarging a binary tree... becomes $(n+1)+1=n+2$. Therefore the number of leaves minus the number of full nodes is given by $(n+2)-(n+1)=1$ as desired, and so by induction the theorem is true for all values of $n$." $\endgroup$
    – Stella Biderman
    Mar 21, 2017 at 17:42
  • 1
    $\begingroup$ Thank you for the help. I am following the proof templates provided here, so that is why I am stuck in the mindset of writing proofs in a certain way. This was a great learning experience for me, so I really appreciate your help and guidance. $\endgroup$
    – Cherry_Developer
    Mar 21, 2017 at 18:05

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .