A full node in a binary tree is a node with two children. Prove that the number

Question

A full node in a binary tree is a node with two children. Prove that the number of full nodes in a (non-empty) binary tree is one less than the number of leaves. Submit your proof as a pdf-file Ass2Proof.pdf.

Please note: You don’t have to provide a formal mathematical proof. However, your proof should demonstrate understanding of the key ideas behind this proof, and an ability to explain technical issues using English language.

Programming Language: Python

Hint: It is a good idea to use a process called “Structural induction”

Show that the claim is valid for a tree with one node (i.e. just the root)

Assume the claim is valid for a tree with n nodes.

Now show that the claim is valid for a tree with (n+1) nodes. In order to show this, consider any leaf node of the tree. Removing the leaf will give a tree with n nodes. With our assumption for that tree the number of full nodes is one less than the number of leaves. Now show that by adding the leaf back the number of full nodes is still one less than the number of leaves.

Explanation / Answer

This recurrence relation describes the relationship between a the number of full nodes F(n)F(n) and the number of leaves nn:

F(n)={1F(n1)+1if n=2if n>2F(n)={1if n=2F(n1)+1if n>2

I will now represent this recurrence relation in what I suspect is its closed form:

G(n)=n1G(n)=n1

Now, I if can prove that F(n)=G(n)F(n)=G(n), then I have proved that the number of full nodes is always one less than the number of leaves.

Basis:
G(2)=21=1G(2)=21=1

Inductive Hypothesis:
F(k)=G(k)=k1F(k)=G(k)=k1, where n=kn=k , to show:
F(k+1)=k+11=kF(k+1)=k+11=k

Inductive Step:

F(k+1)=F((k+1)1)+1=F(k)+1=G(k)+1=(k1)+1=k F(k+1)=F((k+1)1)+1=F(k)+1=G(k)+1=(k1)+1=k

It looks like I've proved that F(n)=G(n)F(n)=G(n), but I feel like I haven't properly associated the original recurrence relation F(n)F(n) with the tree itself.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.