'''
Name: Maggie Yu
PennKey: 19438439
Hours of work required: 5
'''

'''
In all functions below, the keyword "pass" is used to
indicate to the interpreter that the corresponding codeblock
is empty. This is necessary in order for the interpreter
not to consider empty code blocks as syntax errors.
You will replace each of these "pass" keywords by your
code completing the function as described in the comments.
'''


class Node:
    def __init__(self, key):
        '''
        Construct an instance of the Node class
        args:
            key: the key for the node
        args: None
        '''
        self.num = key
        self.l_child = None
        self.r_child = None

class BST:
    def __init__(self):
        '''
        Construct an instance of the BST class
        args: None
        Note: the BST should be initially empty
        '''
        self.root = None
        self.size = 0

    def isempty(self):
        '''
        Whether the tree is empty
        args: None
        ret:
            True if the tree is empty, False otherwise
        '''
        if self.size == 0: return True
        else: return False

    def add(self, key):
        '''
        Add a node to the BST with a given key
        args:
            key: the key to insert in the BST
        ret: None

        Notes: if the key is already in the BST, you
        must silently ignore it (i.e., without raising
        an exception). If you are interested, you may
        want to look into issuing a warning.
        '''
        self.ip = Node(key)
        if self.size == 0:
            self.root = self.ip
        else:
            add_helper(self.root, self.ip)
        self.size = self.size + 1


    def delete(self, key):
        '''
        Remove the node with a matching key from the BST
        args:
            key: the key to delete
        ret: None

        Notes: if the key is not present in the BST, you
        must raise a ValueError exception with a descriptive
        message.
        '''
        l = list(self)
        if key in l:
            og = del_helper_find(self.root, self.root, key, l)
            og = del_helper(self.root, self.root, key, l)
        else:
            raise ValueError()
        self.size = self.size - 1
        return og

    def __iter__(self):
        '''
        A generator for iterating over the values of the key
        args: None
        Note: You should use a combination of yield and yield
        from in order to iterate over the tree.
        '''
        yield from iter_helper(self.root.l_child)
        yield self.root.num
        yield from iter_helper(self.root.r_child)


    def __contains__(self, key):
        '''
        Whether the given key is in the BST
        args:
            key: the key to search for
        ret:
            True if the key is in the BST, false otherwise
        '''
        pass

    def __len__(self):
        '''
        The number of elements in the BST
        args: None
        ret:
            The number of elements in the BST

        Note: you should avoid traversing the BST in this function
        '''
        return self.size


def add_helper(node, new_node):
    if new_node.num > node.num:
        if node.r_child == None:
            node.r_child = new_node
        else:
            add_helper(node.r_child, new_node)

    elif new_node.num < node.num:
        if node.l_child == None:
            node.l_child = new_node
        else:
            add_helper(node.l_child, new_node)

def del_helper_find(base, root, del_num, node_list):
    if root.num == del_num:
        return root
    elif root.num > del_num:
        del_helper_find(base, root.r_child, del_num, node_list)
    elif root.num < del_num:
        del_helper_find(base, root.l_child, del_num, node_list)
            # del_shift(node)

def del_helper(base, root, del_node, node_list):
    if root.l_child == None and root.r_child == None:
        root = None
    elif root.l_child == None:
        root = root.r_child
        return root
    elif root.r_child == None:
        root = root.l_child
    else:
        a = node_list.index(del_node.num)
        b = node_list[a+1]
        del_helper_find(base, base, b, node_list)



def iter_helper(node):
    if node != None:
        yield from iter_helper(node.l_child)
        yield node.num
        yield from iter_helper(node.r_child)








def main():
    '''
    Use this for testing! Make sure to be thorough and test for
    corner cases. There are many corner cases to look out for
    when working with trees!
    '''
    my_tree = BST()
    my_tree.add(1)
    print(my_tree)
    my_tree.add(10)
    my_tree.add(2)
    my_tree.add(3)
    my_tree.add(4)
    my_tree.add(999)
    my_tree.delete(1)
    print(list(my_tree))
    # for elem in my_tree:
        # assert elem in my_tree
    # print(iter(my_tree.root))
    l = iter(my_tree)
    print(next(l))
    print(next(l))

if __name__ == '__main__':
    '''
    This calls the function main() when executing python3 hw3.py
    '''
    main()