1. Engineering
  2. Computer Science
  3. does this proof have a flaw if so explain the...

Question: does this proof have a flaw if so explain the...

Question details

Proof? By induction on number of internal nodes. For2 0, 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)

Does this proof have a flaw, if so explain the flaw in the proof.

Solution by an expert tutor
Blurred Solution
This question has been solved
Subscribe to see this solution