> For the complete documentation index, see [llms.txt](https://emory.gitbook.io/dsa-java/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://emory.gitbook.io/dsa-java/binary-search-trees/exercises.md).

# 4.4. Quiz

## Interpretation

* Explain how the `remove()` method works in the [`AbstractBalancedBinarySearchTree`](https://github.com/emory-courses/dsa-java/blob/master/src/main/java/edu/emory/cs/tree/balanced/AbstractBalancedBinarySearchTree.java) class:
  * Explain what gets assigned to `lowest` in [`L71`](https://github.com/emory-courses/dsa-java/blob/master/src/main/java/edu/emory/cs/tree/balanced/AbstractBalancedBinarySearchTree.java#L71).
  * Explain how the `balance()` methods in [`AVLTree`](https://github.com/emory-courses/dsa-java/blob/master/src/main/java/edu/emory/cs/tree/balanced/AVLTree.java) and [`RedBlackTree`](https://github.com/emory-courses/dsa-java/blob/master/src/main/java/edu/emory/cs/tree/balanced/RedBlackTree.java) keep the trees balanced (or fails to keep them balanced) after a removal.
* Write a report including your explanation and save it as `quiz4.pdf`.

## Implementation

* Create the [`BalacnedBinarySearchTreeQuiz`](https://github.com/emory-courses/dsa-java/blob/master/src/main/java/edu/emory/cs/tree/balanced/BalancedBinarySearchTreeQuiz.java) class under the [`tree.balanced`](https://github.com/emory-courses/dsa-java/blob/master/src/main/java/edu/emory/cs/tree/balanced) package that inherits [the`AbstractBalancedBinarySearchTree`](https://github.com/emory-courses/dsa-java/blob/master/src/main/java/edu/emory/cs/tree/balanced/AbstractBalancedBinarySearchTree.java) class.
* Override the `balance()` method that first checks the following conditions:
  * `node` is the only child &
  * `node`’s parent is the right child of `node`'s grand parent &
  * `node`’s uncle has only one child.
* If all of the above conditions are satisfied, `balance()` makes multiple rotations such that the left subtree is always full before any node gets added to the right subtree.
* For the example below, after adding the keys (in red) to the trees `1`, `2`, `3`, and `4`, they all need to be transformed into the tree `5` by the `balance()` method.
* The transform must be performed only by rotations; other setter methods such as `setLeftChild()` or `setRightChild()` are not allowed in this assignment.

![](/files/-MIubC4iV14KhiZuedMD)