""" QUESTION 3: Binary Search Tree

6 marks, ~15 minutes

In this question, we define a "balanced" binary search tree as a BST that satisfies the following property:

For EVERY node in the BST, the sizes of its left subtree and right subtree differ by at most 1.

(Note again that the "size" of a subtree is the number of nodes in it)

Below, you're given a BinarySearchTree class. You are NOT ALLOWED to modify this class in any way. Do NOT use any attribute/method that is not provided in the class (such as insert(), delete()).

Your job is to implement a top-level function (i.e., not a method of the BinarySearchTree class) named build_balanced_bst() that takes a SORTED list of integers and returns a balanced BST containing all values in the list. For example, build_balanced_bst([1, 2, 3, 4, 5, 6]) should return the following tree:

4 / \ 2 6 / \ / 1 3 5

Read the docstring of build_balanced_bst() carefully and complete the function.

Estimated number of lines of code to write: about 10 to 15 lines. """

from __future__ import annotations from typing import Optional, List # No other import is allowed

class BinarySearchTree: """ Binary Search Tree class. Note that root, left, and right are *public* attributes

DO NOT MODIFY THIS CLASS! """ root: Optional[int] left: Optional[BinarySearchTree] right: Optional[BinarySearchTree]

def __init__(self, root: Optional[int]) -> None: """ Initialize a new BST containing only the given root value. If 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 build_balanced_bst(lst_sorted: List[int]) -> BinarySearchTree: """ Return a balanced BinarySearchTree containing all values in

Preconditions: - is SORTED in an increasing order - len(lst_sorted) >= 0 - all values in are distinct, i.e., no duplicate values

TODO: Complete this function below. Part of the code is given to help you get started

Hint: this function should be recursive. You probably don't need a helper function, but you can add it if you want. """

# Base case: given an empty list, return an empty BinarySearchTree if len(lst_sorted) == 0: return # _______ TODO: fill in this return value

# Recursive case: lst_sorted is not empty # Break lst_sorted into different parts # Make recursive calls to build subtrees # Combine subtrees into the big tree to return # TODO: Complete the recursive case below.