Let us define a full node in a binary tree to be a node that has two children. For a binary tree T, let full( T ) be the number of full nodes in T and let leaves( T ) be the number of leaves in T. Prove by induction on the number of nodes in a binary tree, that leaves( T ) = full( T ) + 1. Hint: consider the cases where the root has two children, one child and zero children.