4. Question 4 is based on Proof by Induction.

We say that a tree is binary if every internal node has exactly two children. Using induction on the size of the tree, prove the following claim: In any binary tree, the number of external nodes (also called as leaves) is one more than the number of internal nodes. (Hints: For the base case, use a tree of size 1. For the induction step, use the fact that the left and right subtrees of the root node are smaller in size.)