Recall from lecture that a binary tree T is either:

1. null (the empty tree); or

2. a root noder with two subtrees T and Tg, both of which are binary trees.

Consider the following algorithm nunLeaves (T) that takes as input a binary tree T and returns the number of leaves in the tree.

Prove by structural induction that for every binary tree T, numLeaves(T) returns the number of leaves of T.