Claim 2. For all n, all full binary trees with n internal nodes have height n -1 We have the following "proof" of the claim Proof. ?? By induction on n. For each n 2 1, let IH(n) be the statement "all full binary trees with n internal nodes have height n -1" 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 only one leaf (which is also the root). Thus the longest root-to-leaf path has length 0, and IH(0) is true. Inductive Step: Let n 2 1 and show that IH(n) implies IH(n + 1). Let T be an arbitrary full binary tree with n internal nodes. Create the binary tree T" having n +1 internal nodes by removing a bottonm leaf node in T and replacing it with an internal node connected to two children that are leaves. The longest root-to-leaf path in T" is thus one greater than the longest root-to-leaf path in T, so the height of T is the height of T plus 1. Furthermore, by the inductive hypothesis IH(n), the height of T is n-1. Therefore T, has n + 1 internal nodes and height n-1 1 n, showing IH(n + 1). Identify and clearly describe the flaw in this proof (4 pts) Now go back to the proof of the first claim. Does it have a flaw (1 pt)? Clearly describe the flaw, or argue that the proof is correct (4 pts)