Remember, "the answer" is only half of it! Also, make sure everyone in your group can explain why.

We will use this Gradescope Online Assignment as our worksheet for in-class work. These problems are coded as being worth points for our simplicity, but will not impact your grade in the course.

Question 2

Question 2.1: Warm up

The first answer is correct.

Since we said to ignore any AVL rotations for this part, we just add values, going left/right down the tree depending on if the value we are inserting is less than or greater than. Once we reach an empty spot, we know where to add the value.

Question 2.2 AVL Invariant

After inserting the value 4, it will go to the right of the 3. The tree looks like the following. We have also include some highlighting for the next question. This violates the AVL Invariant for node 2 since it's left child has height -1 and its right child has height 1.

Question 2.3 AVL Rotation Type

Since the insertion violates the AVL invariant at the node 2, we we know we are going to do a rotation around there. We highlighted the nodes in the last picture to show we are in the "Line" case that is solved with a Left rotation.

Question 2.4 AVL Rotation

Question 3

Question 3.1 AVL Invariant

Yes, this is an AVL Tree!