INDUCTION OF BINARY TREE (8 points) In the following a node is a data type with
ID: 3877653 • Letter: I
Question
INDUCTION OF BINARY TREE
(8 points) In the following a node is a data type with two associated pointers labeled "left" and "right". We call a node a leaf if both the left and right pointers are null. A "good binary tree" has the following recursive definition. A leaf node bt or A node,r, such that r.left and r.right point to distinct gbt's. Prove, using induction, that a gbt with n > 0 leaves, has 2n - 1 nodes in total (i.e. internal and leaf nodes together). Note that every gbt has a root, i.e. a single node 4 points) A "bad binary tree" is defined to also allow for the empty tree. Specifically Null (i.e. the empty tree) or bbt = A leaf node. or A node, r, such that r.left and r.right point to distinct bbt's. Does it hold that a bbt with n > 0 leaves, has 2n 1 nodes in total? If yes, prove it. If no, what is the best upper bound possible on the total number of nodes in terms of nExplanation / Answer
SOLUTION :
A)
TO BE PROVEN : A gbt with n leaves has 2n 1 nodes.
Formally, S(gbt): if gbt is a binary tree with n leaves, then gbt has 2n 1 nodes.
Induction is on the size = number of nodes of gbt .
Basis : If gbt has 1 leaf, it is a one-node tree. 1 = 2x1-1 so OK.
Induction: Assume S(U) for trees with fewer nodes than gbt . In particular, assume for the subtrees of gbt .
gbt must be a root plus two subtrees U and V .
If U and V have u and v leaves, respectively, and T has t leaves, then u + v = t.
By the inductive hypothesis, U and V have 2u-1 and 2v-1 nodes, respectively.
Then T has 1 + (2u-1) + (2v-1) nodes = 2(u + v)-1 = 2t-1, HENCE PROVED