Sale!

Quiz 9 BST method

$30.00

Category:
Rate this product

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)

Quiz 9 BST method
$30.00
Open chat
Need help?
Hello
Can we help?