[SOLUTIONS] Lab 8 Assignment

The University of Michigan Electrical Engineering & Computer Science EECS 281: Data Structures and Algorithms Fall 2023 Lab 8: Binary Trees, AVL Trees, and Tree Traversals Instructions: Work on this document with your group, then enter the answers on the canvas quiz. This assignment is due on November 17th, at 11:59 PM. Note: Be prepared before you meet with your lab group, and read this document so that you know what you must submit for full credit. You can even start it ahead of time and then ask questions during any lab section for help completing it. You MUST include the following assignment identifier at the top of every file you submit to the autograder as a comment. This includes all source files, header files, and your Makefile (if there is one). Project Identifier: EAA16B5C3724FBFD78F132136AABBBBA4952E261 © 2023 Regents of the University of Michigan Page 1 of 11

EECS 281 Lab 8: Binary Trees, AVL Trees, and Tree Traversals 1 Logistics 1. When are lab 7’s autograder and quiz due? A. 11/12/2023 B. 11/08/2023 C. 11/10/2023 D. 11/11/2023 2. When are lab 8’s autograder and quiz due? A. 11/18/2023 B. 11/19/2023 C. 11/15/2023 D. 11/17/2023 3. What is the last day you can submit lab 8’s handwritten problem to an instructor in lab? A. 11/12/2023 B. 11/11/2023 C. 11/10/2023 D. 11/08/2023 4. When is project 3 due? A. 11/17/2023 B. 11/14/2023 C. 11/16/2023 D. 11/15/2023 5. What is the theme of lab 8’s autograder assignment? A. AVL Trees B. Dynamic Programming C. Proving P=NP D. Euchre © 2023 Regents of the University of Michigan Page 2 of 11

EECS 281 Lab 8: Binary Trees, AVL Trees, and Tree Traversals 10. You have a hash table that uses the separate chaining collision resolution method. However, instead of chaining elements using a linked list, this hash table chains elements using an AVL tree (see diagram). What is the worst-case time complexity of searching for an element in this hash table, if it contains n elements? Assume the hash function runs in Θ(1) time. A. Θ(1) B. Θ(log n ) C. Θ( n ) D. Θ( n log n ) E. Θ( n 2 ) Solution: Random access into the correct bin would be Θ(1). Once in the correct bin, searching for the element would be Θ(log n ). Therefore, the overall search is Θ(log n ). © 2023 Regents of the University of Michigan Page 4 of 11

EECS 281 Lab 8: Binary Trees, AVL Trees, and Tree Traversals 11. Consider the following AVL tree: How many tree rotations (with double rotations counting as 2) would occur if the following elements were inserted in the given order: 75, 68, 65, 40? A. 2 B. 3 C. 4 D. 5 E. more than 5 Solution: Double rotation occurs after inserting 75 (Rotate left on 70, then rotate right around 80). Zero rotations occur after inserting 68 (Left child of 70). Single rotation occurs after inserting 65 (Rotate right on 70). Single rotation occurs after inserting 40 (Rotate left on 30). for questions 12-13, consider the following binary trees: 12. Which of the above trees (A, B, C, D, or E) is/are complete binary trees? Select all that apply. A. A B. B C. C D. D E. E Solution: Complete binary trees have every level fully filled, with the possible exception of the lowest level, which is filled left to right. C is still complete, as a single node constitutes a fully filled level. © 2023 Regents of the University of Michigan Page 5 of 11

EECS 281 Lab 8: Binary Trees, AVL Trees, and Tree Traversals 16. Which of the following statements is/are TRUE? Select all that apply. A. finding an arbitrary element in an AVL binary search tree has Θ( n ) worst-case time complexity B. traversing a binary tree can be done in Θ(log n ) time C. inserting an element into a binary search tree has Θ( n ) worst-case time complexity D. an in-order traversal of any BST produces sorted output, even if it is unbalanced E. none of the above statements are true Solution: A is false, as AVL trees have worst case Θ(log n ) search. B is false, as all tree traversals must visit each node, so they must be Θ( n ). C is true, as binary search trees can have a stick structure. D is true (fundamental fact of the BST ordering). 17. Consider the following snippet of code: int mysteryFunction ( struct Node *root) { if (root == nullptr) { return 0; } else if (root ->left == nullptr && root ->right == nullptr) { return 1; } else { return 1 + mysteryFunction (root ->left) + mysteryFunction (root ->right ); } } What does the mysteryFunction do if root is the root of a binary tree? A. it returns the number of leaf nodes B. it returns the number of internal nodes C. it returns the number of nodes in the tree D. it returns the height of the tree E. it returns the depth of the tree F. none of the above Solution: For non-leaf nodes, this function will add 1 to the recursive total and continue the recursion with its children. For leaf nodes, this function will add 1 to the recursive total and terminate. This means the function will be called on every node, and the recursive total will be incremented by one for each call. This counts the number of nodes in the tree. © 2023 Regents of the University of Michigan Page 7 of 11

EECS 281 Lab 8: Binary Trees, AVL Trees, and Tree Traversals 18. Consider the Tree Sort algorithm in which sorting is achieved by placing all elements to be sorted into a binary search tree and then taking the in-order traversal of the tree. Another sorting algorithm, AVL Tree Sort, places all elements into an AVL binary search tree and then takes the in-order traversal of the tree. Which of the following statements is/are TRUE about these sorts? Select all that apply. A. both Tree Sort and AVL Tree Sort perform well on input that is already in nearly sorted order B. the best-case time complexity of Tree Sort is Θ( n log n ) C. the worst-case time complexity of AVL Tree Sort is Θ( n 2 ) D. the best-case space complexity of Tree Sort is Θ( n ) E. the best-case space complexity of AVL Tree Sort is Θ(log n ) Solution: A is false, as a sorted input to a binary search tree will create a stick-like struc- ture, so the insertions will be Θ( n ) instead of Θ(log n ). B is true, as the best case gives n insertions, each Θ(log n ). C is false, as AVL Tree Sort will always be Θ( n log n ) due to the AVL invariant. D is true, because Tree Sort will need to store n elements. E is false, because AVL Tree Sort will need to store n elements. © 2023 Regents of the University of Michigan Page 8 of 11

EECS 281 Lab 8: Binary Trees, AVL Trees, and Tree Traversals 4 Coding Assignment You can work on these problems by yourself or with your group, but a solution must be submitted to the autograder for each individual. Ro-Tater Tots For this lab, finish the implementation of an AVL tree class. In the average case, unbalanced binary search trees attain Θ(log n ) time operations, but their worst case is Θ( n ). For this problem, you are tasked with completing the implemen- tation for an AVL tree, which attains Θ(log n ) time in the worst case. Searching has been completed for you (it’s exactly the same as in an ordinary BST). You’re given an AVL tree class with the following Node struct type (in the avl lab.h file ): struct Node { int datum; int height; Node* left; Node* right; int left_height () { return left ? left ->height : 0; } int right_height () { return right ? right ->height : 0; } int balance () { return left_height () - right_height (); } // when the height of its children change , call this function // to recalculate the height of this node , the parent void fix_height () { height = 1 + max( left_height (), right_height ()); } }; Note that this is really just a node with a datum, height, left, and right; it also has some helper functions to handle height and balance. For this problem, you will implement three functions: // insert_node returns the new root of this subtree after inserting datum. // if datum already exists in the tree , the copy is inserted to its right. AVL:: Node* AVL :: insert_node (AVL :: Node* node , int datum ); // rotate_left performs a left rotation; // it returns the new ' root ' of the rotated subtree // (remember to update the heights of nodes !) // you may assume that it has a right child AVL:: Node* AVL :: rotate_left (AVL :: Node* node ); // rotate_right performs a right rotation; // it returns the new ' root ' of the rotated subtree // (remember to update the heights of nodes !) // you may assume that it has a left child AVL:: Node* AVL :: rotate_right (AVL :: Node* node ); You may define any helpers functions or methods that you like, although you can complete the lab without any. © 2023 Regents of the University of Michigan Page 10 of 11

EECS 281 Lab 8: Binary Trees, AVL Trees, and Tree Traversals To help you debug your implementation, a tree-printing utility has been implemented for you. main() will construct 3 different AVL trees using your code and print them. The correct tree structures for these 3 trees are given as comments in main(). If the diagrams your program prints look different, there’s a bug in your code! Submission Add you and (if you have one) your partner’s names as a comment near the top of the avl lab.h file. To submit to the autograder, run make fullsubmit and submit the fullsubmit.tar.gz file that is created. If you are working with a partner, both partners must submit to the autograder. Only students who submit code to the autograder will receive points. It’s fine if both of you submit the same code for this assignment. Your program will be judged on 10 different test cases, similar to the ones provided to you in the avl lab.cpp file. These test cases will involve searching for a number in a large AVL tree. You can infer the following from the autograder test case names: • a test case beginning with L means that the number is located to the left of the root • a test case beginning with R means that the number is located to the right of the root • a test case with the letter M indicates that the number cannot be found in the tree • a test case with the letter X indicates that the number can be found in the tree © 2023 Regents of the University of Michigan Page 11 of 11