Problem 3. Induction onBinaryTrees (a) (8 points) In the following a node is a d

Question

Problem 3. Induction onBinaryTrees (a) (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 with no incoming pointers. b) (4 points) A "bad binary tree" is defined to also allow for the empty tree. Specifically, Nul (i.e. the empty tree) A leaf node A node, r, such that r.left and r.right point to distinct bbt's. or bbt or 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 ofn

Explanation / Answer

Imagine a tree, this has n=1 leaves and 2 nodes but the formula gives 2n1=1 nodes.

Let's make this assumption, to prove by induction,

notice (1) that the formula holds true for a tree of height 1 with 1 node, because of 2×11=1.

Then (2) assume that the formula holds for trees with k leaves, so assume trees with k leaves have 2k1 nodes.

Adding another level to the tree with k leaves adds other 2k leaves because each leaf in the original tree has 2 children.

So this new tree has a total of (2k1) leaves from the original plus other 2k leaves = 4k1 leaves.

The formula for 2k leaves gives 2(2k)1=4k1 leaves, which is the same!

So because our (1) our base step is true; and (2) our inductive step is true, then the formula is true for all nodes.

Alternatively, the depth d of the tree is log2 (n+1) because the number of nodes doubles at each level.

The total number of nodes is 1+2+4+…with d terms in the sum or 20+21+2 2+…+2d1. By the geometric series formula, the sum is equal to

(2d-1) / (2-1)=2log(n+1)-1

=2*2log(n)-1

=2n-1

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.