Recall from Definition 5.16 that we defined a binary tree a 1. an empty tree, denoted by null; or 2. a root node x, a left subtree Tℓ, and a right subtree Tr , where x is an arbitrary value and Tℓ...

Recall from Definition 5.16 that we defined a binary tree a

1. an empty tree, denoted by null; or

2. a root node x, a left subtree Tℓ, and a right subtree Tr , where x is an arbitrary value and Tℓ and Tr are both binary trees.

Recall further that a leaf of a binary tree T is a node in T whose left subtree and right subtree are both null. Prove by structural induction that the algorithm countLeaves(T) in Figure 5.38 returns the number of leaves in a binary tree T.

Figure 5.38: An algorithm to count leaves in a binary tree.