Quiz 9 BST method

Quiz 9
We've defined a BST method for you to implement below named closest.
In this method, we've given you a basic sketch of the different scenarios
you'll need to consider.

Your tasks are listed below.
    1. Implement the base case (when the BST is empty).
    2. Implement the case where the item == the root.
    3. Implement the case where item < root.
    4. Implement the case where item > root.

You may not add any additional methods to the BST.
We suggest you draw a BST and walk through an example before implementing this
method. Below is an example:
                         10
                      /     \
                    3        32
                  /  \\      /  \
                2     7   27    81
                               /  \
                             49    99

[Not graded] It may help to think through the following questions:
    - What is the expected result of BST.closest(20)?
    - What is the expected result of BST._left.closest(20)?
    - What is the expected result of BST._right.closest(20)?
    - Can the result of BST._left.closest(20) ever be closer to 20 than the
      root of our BST?

Submit your code on MarkUs and run the automated self-test.
Your grade on the quiz will be based solely on the results of the self-test.
(i.e. if you pass all of the tests, you get full marks on the quiz.)
"""
from __future__ import annotations
from typing import Optional, Any


class BinarySearchTree:
    """Binary Search Tree class.

    This class represents a binary tree satisfying the Binary Search Tree
    property: for every item, its value is >= all items stored in its left
    subtree, and <= all items stored in its right subtree.
    """
    # === Private Attributes ===
    # The item stored at the root of the tree, or None if the tree is empty.
    _root: Optional[Any]
    # The left subtree, or None if the tree is empty.
    _left: Optional[BinarySearchTree]
    # The right subtree, or None if the tree is empty.
    _right: Optional[BinarySearchTree]

    # === Representation Invariants ===
    #  - If self._root is None, then so are self._left and self._right.
    #    This represents an empty BST.
    #  - If self._root is not None, then self._left and self._right
    #    are BinarySearchTrees.
    #  - (BST Property) If self is not empty, then
    #    all items in self._left are <= self._root, and
    #    all items in self._right are >= self._root.

    def closest(self, item: int) -> Optional[int]:
        """Return the value in this BST that is closest to <item>.

        By "closest" we mean the value that minimizes the absolute difference
        between itself and <item>. For example, if a tree contains 90, 100,
        and 115, the value closest to 104 is 100.

        If there is a tie, return the smaller value.
        Return None if this BST is empty.

        Precondition: this BST contains only integers.
        """
        if self.is_empty():
            return None
        elif item == self._root:
            return self._root
        elif item < self._root:
            # dif = abs(self._root - item)
            left_closest = self._left.closest(item)
            if left_closest is None:
                return self._root
            elif abs(left_closest - item) > abs(self._root - item):
                return self._root
            else:
                return left_closest
        else:
            right_closest = self._right.closest(item)
            if right_closest is None:
                return self._root
            elif abs(right_closest - item) >= abs(self._root - item):
                return self._root
            else:
                return right_closest


    ############################################################################
    # Below are the other BST methods that are available to you.
    # Do NOT modify these methods.
    ############################################################################
    def __init__(self, root: Optional[Any]) -> None:
        """Initialize a new BST containing only the given root value.

        If <root> is None, initialize an empty tree.
        """
        if root is None:
            self._root = None
            self._left = None
            self._right = None
        else:
            self._root = root
            self._left = BinarySearchTree(None)
            self._right = BinarySearchTree(None)

    def is_empty(self) -> bool:
        """Return whether this BST is empty.

        >>> bst = BinarySearchTree(None)
        >>> bst.is_empty()
        True
        >>> bst = BinarySearchTree(10)
        >>> bst.is_empty()
        False
        """
        return self._root is None

    # You should not be using insert, but you may want to use it to test your
    # code.
    def insert(self, item: Any) -> None:
        """Insert <item> into this tree.

        Do not change positions of any other values.

        >>> bst = BinarySearchTree(10)
        >>> bst.insert(3)
        >>> bst.insert(20)
        >>> bst._root
        10
        >>> bst._left._root
        3
        >>> bst._right._root
        20
        """
        if self.is_empty():
            # Make new leaf.
            # Note that self._left and self._right cannot be None when the
            # tree is non-empty! (This is one of our invariants.)
            self._root = item
            self._left = BinarySearchTree(None)
            self._right = BinarySearchTree(None)
        elif item <= self._root:
            self._left.insert(item)
        else:
            self._right.insert(item)