2. Induction Proof correctness (10 pts) Recall that a full binary tree contains (A) just a single leaf node, or (B) is an internal node (the root) connected to two disjoint subtrees, which are themselves full binary trees First consider the following claim and proof. Think about if the theorem is true or not, and if the proof is correct or not. (These preliminary thoughts need not be included in your answer.) Claim 1. In any full binary tree, the number of leaf nodes is one greater than the number of internalt nodes Proof.??) By induction on number of internal nodes. For all n 20, let IH(n) be the statement: "all full binary trees having exactly n internal nodes have n +1 leaf nodes." Base Case: Show IH(0). Every full binary tree with zero internal nodes is formed by case (A) of the definition, and thus consists of just a single leaf node. Therefore, every full binary tree with 0 internal nodes has exactly 1 leaf node, and IH(0) is true. Inductive Step: Assume k > 0 and IH(k) holds to show that IH(k +1) also holds. Consider an arbitrary full binary tree T with k internal nodes. By the inductive hypothesis T has k 1 external nodes. Create a k +1 internal node tree T' by removing a bottom leaf node in T and replacing it with an internal node connected to two children that are leaves. T" has one more internal node than T, and 2-1 = 1 more external node than T. Therefore T, has k + 1 internal nodes and (k +1)+1- k+2 external nodes, proving P(k +1) Now consider the following claim. Give a counter-example showing that the claim is false (1 pt). Recall that the height of a binary tree is the length of the longest root-to-leaf path)