Question

a binary tree is full if all of its vertices have either zero or two children. let bn denote the number of full binary trees with n vertices. (a) by drawing out all full binary trees with 3, 5, or 7 vertices, determine the exact values of b3, b5, and b7. why have we left out even numbers of vertices, like b4? (b) for general n, derive a re

Answer 1

Step-by-step explanation:

A binary tree is full if all of its vertices have either zero or two children. LetBndenote the number of fullbinary trees with n vertices.(a) By drawing out all full binary trees with 3, 5, or 7 vertices, determine the exact values ofB3,B5, andB7. Why have we left out even numbers of vertices, likeB4? (3 points: 2 points for exact values + 1point for reason)(b) For generaln, derive a recurrence relation forBn. (3 points)(c) Show by induction thatBnisΩ(2n). (4 points)Solution 1.Clarification: Assume that identical keys are stored in all the nodes of binary tree(a) B3 = 1, B5 = 2, B7 = 5. Any full binary tree must have an odd number of vertices, as it has an evennumber of vertices that are children of some other vertex and a single root. HenceB2k= 0for all k.(b) We can write the recurrence relation by decomposing the tree into subtrees rooted at the children of root.For a tree withnnodes, the number of nodes in left subtree and right subtree wil vary as1,3,5, . . . , n-2andn-2, n-4. . . ,1respectively. Therefore, the recurrence relation forBnwill be as follows:Bn=n-2Xi=1BiBn-1-i(1)(c) We need to show thatBn≥C2nfor alln≥nowhereC, no>0Assume thatBk≥C2kfor all odd values1,3. . . K. We will show thatBk+2≥c2k+2.Consider the recurrence relation forBk+2.Bk+2=kXi=1BiBk+1-i(2)Bk+2≥C2i×C2k+1-i×(k+ 1)/2(3)Bk+2≥C2k+1×C(k+ 1)/2(4)We can chooseCandn0appropriately such thatC(k+ 1)/2≤2andBk+2≥C2k+2Question 2.(10 points: 5 points for correct algorithm, 3 points for proof of correctness, 2 points for proofof runtime)Given a sorted array of distinct integersA[1, . . . , n], you want to find out whether there is an indexiforwhichA[i] =i. Give a divide-and-conquer algorithm that runs in timeO(logn).