# BST exercice

# This implementation is strictly defined by the conditions in the __init__
# A valid array: [10, 3, 15, 1, None, 9]

class BinarySearchTree():
    @staticmethod
    def is_valid_array(bst_array):
        # TODO: Validates that the array is a valid bst
    
    def __init__(self, bst_array):
        """
        Initialise a bst with an array that satisfies the following conditions
        1. bst[2*i + 1] === (None or KeyError) or bst[i] >= bst[2*i + 1]
        2. bst[2*i + 2] === (None or KeyError) or bst[i] <= bst[2*i + 2]
        """
        if not self.is_valid_array(bst_array):
            raise ValueError("Invalid tree")

        self.internal_array = bst_array

    
    def exists(self, value):
        # TODO: Returns true if the element exists
    
    def add(self, value)
        # TODO: adds the value to the tree

    def smallest(self):
        # TODO: should return the smallest element

    def biggest(self):
        # TODO: should return the biggest element

    def sorted_array(self):
        # TODO: should return a sorted array

# How would you optimise this tree ?
# TODO: answer in text, code is not required