Recitation #3CS430 Spring 2021Will start soon..1TodayQuiz 1 has been graded • Grader: Qitian <[email protected]>• Sample solutionQuiz 2 has not been graded• Grader: TBD• Sample solutionExercise (old quiz): Proof by induction2Quiz 1Problem 1 You are given a linked list represented by the following data structure.Nodes have two fields: element, and next-node. The element is an integer. The next-node field is NIL/NULL for the last node in the list. You are given the location (orpointer) of the first node. Write a function with input parameter the location of thefirst node of the list (or pointer to that node), and that computes the average value ofthe elements in list.For the following list, the average value of the elements is 14/4.Do not forget a special case where the pointer given is NIL/NULL.33 6 4 1Quiz 1Problem 1 You are given a linked list represented by the following data structure.Nodes have two fields: element, and next-node. The element is an integer. The next-node field is NIL/NULL for the last node in the list. You are given the location (orpointer) of the first node. Write a function with input parameter the location of thefirst node of the list (or pointer to that node), and that computes the average value ofthe elements in list.Average(x)1. if x == NIL2. return -1 // error3. else4. total = 05. size = 06. while x != NIL7. total = total + x.element8. size = size + 19. x = x.next-node10. return total/size43 6 4 1Quiz 2Problem 2 You are given a rooted binary tree represented by the following datastructure. Nodes have three fields: element, left-child, and right-child. The elementis a number. The left-child or right-child fields are NIL/NULL if a node has no left-child or right-child respectively. Write a (recursive) function with input parameterthe location of a node (or pointer to the node), and that computes the average valueof the elements in the subtree rooted by that node. See an example below.5Quiz 2 (sample solution with two functions)Average(x)1. if x == NIL2. return -1 // error3. else4. (total, size) = Average-Rec(x)5. return total/sizeAverage-Rec(x)1. if x == NIL2. return (0, 0) // base case3. else4. (left-total, left-size) = Average-Rec(x.left-child)5. (right-total, right-size) = Average-Rec(x.right-child)6. total = x.element + left-total + right-total7. size = 1 + left-size + right-size8. return (total, size)6Quiz 2 (sample solution with a recursive function)Average(x)1. if x == NIL2. return (-1, -1)3. else4. (left-average, left-size) = Average(x.left-child)5. (right-average, right-size) = Average(x.right-child)6. total = x.element7. size = 18. if left-size != -19. size = size + left-size 10. total = total + left-average*left-size11. if right-size != -112. size = size + right-size13. total = total + right-average*right-size14. return (total/size, size)7ExerciseProblem Show by induction that the number of nodes that have two children in anon-empty binary tree is 1 less than the number of leaves.Consider a binary tree from Quiz 2 as an example. The number of nodes that havetwo children is 2, while the number of leaves is 3.8ExerciseProblem Show by induction that the number of nodes that have two children in anon-empty binary tree is 1 less than the number of leaves.Structure of Proof by inductionStatement: involves a number nBase case: prove that the statement holds for the base case (typically n=0 or n=1)Induction step: prove that if the statement holds for n=k (induction hypothesis),then it also holds for n=k+1What should n represent in this problem?9ExerciseProblem Show by induction that the number of nodes that have two children in anon-empty binary tree is 1 less than the number of leaves.Proof by inductionStatement: The number of nodes that have two children in a non-empty binary treeof size n is 1 less than the number of leavesBase case: (n=1)A non-empty binary tree of size 1 contains only the root, and it has 0 nodes thathave two children and 1 leaf. The statement holds.10We have two cases for adding a new node:Case 1: the parent of the new node is a leaf node in T.• The number of leaves remains the same because the parent becomes anon-leaf node, and the new node becomes a leaf node in T’.• The number of nodes that have two children also remains the same.Case 2: the par ent of the new node has one child in T.• The number of leaves increases by one.• The number of nodes that have two children also increases by one.In either case, the difference between t he number of nodes with twochildren and the number of leaves does not change. Therefore, if thestatement holds for T, then the statement also holds for T’11Proof by induction (cont.)Statement: The number of nodes that have two children in a non-empty binary tr ee of sizen is 1 less than the number of leavesInduction step:Let T be a non-empty binary tree of size k. Consider another binary tree T’ of size k+1 inwhich a new node is added to one of nodes in T. We show that if the statement holds for Tthen the statement also holds for