INDUCTION OF BINARY TREE

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 n