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 dont 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.