1. Section 5.1.1 claims that a full binary tree has the highest number of leaf nodes among all…

1. Section 5.1.1 claims that a full binary tree has the highest number of leaf nodes among all trees with n internal nodes. Prove that this is true.

2. Define the degree of a node as the number of its non-empty children. Prove by induction that the number of degree 2 nodes in any binary tree is one less than the number of leaves.