python3 A full node in a binary tree is a node with two chil

A full node in a binary tree is a node with two children. Prove that the number of full nodes in a (nonempty) binary tree is one less than the number of leaves Submit jour proof as a pdf-file Ass 2 proof.pdf.

Solution

Let the number of nodes in the last level of nodes = n

Therefore, the number of leaves = 2n.

The total number of inner nodes = n + n/2 + n/4 + ... + 1

= n(1-(1/2)^log₂(n/2))/1-(1/2)     [Sum of GP]

= 2n - n * (2^-1)^log₂(n)

=2n - n * 2^log₂(1/n)

=2n - n/n

=2n - 1

= Number of leaves - 1

Hence, proved