BST

# Do not edit the class below except for
# the insert, contains, and remove methods.
# Feel free to add new properties and methods
# to the class.
class BST:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

    def insert(self, value):
        # Write your code here.
        # Do not edit the return statement of this method.
        current = self
        while current:
            if value >= current.value:
                if not current.right:
                    current.right = BST(value)
                    break
                current = current.right
            elif value < current.value:
                if not current.left:
                    current.left = BST(value)
                    break
                current = current.left 
        return self
    
    def contains(self, value):
        # Write your code here.
        cur, _ = self.find(value)
        if cur and cur.value == value:
            return True   
        return False
   
    def find(self, value):
        current = self
        parent = None
        while current:
            if value == current.value:
                return current, parent
            if value < current.value:
                parent = current
                current = current.left
            else:
                parent =current
                current = current.right
                
        return current, parent
   
    def minBST(self, subtree):
        #finds minimum in the subtree, returns its value and removes it!
        current = subtree
        parent = None
        min_val = None
        while current:
            if current.left:
                parent = current
                current = current.left
            else:
                min_val = current.value
                if parent:
                    parent.left = current.right
                   
                return min_val, parent
               
       
    def remove(self, value):
        if not self or (not self.left and not self.right):
            return self
        #find the node to remove
        current = self
        parent = None
        root = self
        current, parent = self.find(value)
        if current.value != value:
            return self
        # node to be removed has no children
        if not current.left and not current.right:
            if parent.right == current:
                parent.right = None
            else:
                parent.left = None
        # node to be removed has one children
        elif current.left and not current.right:
            if parent:
                if parent.left == current:
                    parent.left = current.left
                else: 
                    parent.right = current.left
            else:
                current.value = current.left.value
                current.left = current.left.left
                
        elif current.right and not current.left:
            if parent:
                if parent.left == current:
                    parent.left = current.right
                else:
                    parent.right = current.right
            else:
                current.value = current.right.value
                current.right = current.right.right
                #current = current.right wrong
                
        # node to be removed has two children
        else:
            print(current.left.value)
            substitute_val, parent = self.minBST(current.right) #handles the substitute removal too!
            current.value = substitute_val
            if not parent:
                current.right = current.right.right