import re

class BTNode:
    def __init__(self, val):
        self.val = val
        self.left = None   # less than 
        self.right = None  # greater than or equal 
        self.parent = None 

class BST:
    def __init__(self):
        self.root = None 
        
    def add(self, val):
        bt_node = BTNode(val)    

        if self.root == None:
            self.root = bt_node
        else: 
            node = self.root 
            prev = None 

            while node:
                prev = node 
                if val >= node.val:
                    node = node.right 
                    if node == None:
                        
                        prev.right = bt_node  
                        prev.right.parent = prev
                else:
                    node = node.left 
                    if node == None:
                        prev.left = bt_node
                        prev.left.parent = prev

    def contains(self, val):
        node = self.root 
        while node:
            if val == node.val:
                return True 
            elif val > node.val :
                node = node.right 
            else: 
                node = node.left 
        return False 

    def min(self):
        node = self.root 
        
        while node.left:
            node = node.left 
        return node.val
    
    def max (self):
        node = self.root 

        while node.right:
            node = node.right 
        return node.val 
    
    def size(self): 
        q = [self.root]
        count = 0 

        while q:
            node = q.pop(0)

            if node:
                count += 1
                q.append(node.left)
                q.append(node.right)
            
        return count 
    
    def is_empty(self):
        return self.size() == 0

    def height(self):
        class height_node:
            def __init__(self, root = None):
                self.height = 0
                self.bst_node = root 
        
        def clone(parent):
            c_node = height_node()
            c_node.height = parent.height 
            c_node.bst_node = parent.bst_node 
            return c_node 
        
        q = [height_node(self.root)]
        
        height_out = 0 

        while q:
            node = q.pop() 

            if node.bst_node:
                node.height += 1
                
                if node.height > height_out:
                    height_out = node.height

                #left 
                new_node = clone(node)    
                new_node.bst_node = new_node.bst_node.left 
                q.append(new_node)
                
                # right 
                new_node = clone(node)
                new_node.bst_node = new_node.bst_node.right 
                q.append(new_node)

        return height_out

    def is_balanced(self):
        # use height method above 
        root = self.root 
        left = None 
        right = None 

        self.root = root.left 
        left = self.height()

        self.root = root.right 
        right = self.height() 
        right = self.height()
        
        print(right, left)
        # set root back to original
        self.root = root 
        
        return abs( left - right) <= 1

    def min_height(self):
        class h_node:
            def __init__(self, parent = None):
                self.bst_node = parent 
                self.height = 0
        
        if self.root == None:
            return 0
        
        queue = [h_node(self.root)]
        
        min_height = None 

        while queue:
            node = queue.pop()

            if node.bst_node.left == None and node.bst_node.right == None:
                if min_height == None:
                    min_height = node.height
                if node.height < min_height:
                    min_height = node.height 

            if node.bst_node.left:
                new_node  = h_node(node.bst_node.left)
                new_node.height = node.height + 1
                queue.append(new_node)

            if node.bst_node.right:
                new_node = h_node(node.bst_node.right)
                new_node.height = node.height + 1
                queue.append(new_node)

        return min_height

    def remove(self, val):
        node = self.root 
        prev = None 
        
        if node == None:
            return node
        
        while node:

            if node.val == val:
                
                # leaf
                if node.left  == None and node.right == None:
                    
                    if self.root == node:
                        self.root = None 
                    elif prev.left == node:
                        prev.left = None 
                    elif prev.right == node:
                        prev.right = None 
                    del(node)
                    break

                # delete root 
                if prev == None:
                    if node.right == None:
                        self.right = node.left
                    elif node.left == None:
                        self.root = node.right 
                    else:
                        left_root_node = node.left 
                        right_root_node = node.right 
                        left_right_detached_node = node.left.right 
                        right_left_deep_node = self.root 
                        right_left_deep_node = right_left_deep_node.right 
                        while right_left_deep_node.left :
                            right_left_deep_node = right_left_deep_node.left 
                        left_root_node.right = right_root_node
                        right_left_deep_node.left = left_right_detached_node
                        self.root = left_root_node 
                        del(node)
                        break 

                # left delete ( right rotate)
                elif prev.left == node:         

                    left_right_detached_node = node.left.right
                    
                    if node.right == None:
                        node.right = left_right_detached_node 
                    else:
                        right_left_deep_node = node.right
                        while right_left_deep_node.left:
                            right_left_deep_node = right_left_deep_node.left 
                        right_left_deep_node.left = left_right_detached_node 
                    prev.left = node.left
                    del(node)
                    break 

                # right delete (left roatate) 
                elif prev.right == node:
                    right_left_detach_node = node.right.left
                    prev.right = node.right

                    if node.left == None:
                        node.left = right_left_detach_node
                    else:
                        left_right_deep_node = node.left
                        while left_right_deep_node.right:
                            left_right_deep_node = left_right_deep_node.right 
                        left_right_deep_node.right = right_left_detach_node 
                    prev.right = node.right 
                    del(node)
                    break

            elif val <  node.val and node.left !=  None :
                
                prev = node 
                node = node.left 

            elif val > node.val and  node.right != None :
                prev = node 
                node = node.right 

            # value not found 
            else:
                node = node.left 


    def remove_all(self):

        if self.root == None:
            return None 
        
        stackA = [self.root]
        stackB = []
        
        while  stackA or stackB:
            
            # stack A has priority 
            if stackA:
                node = stackA.pop()
            elif stackB:
                node = stackB.pop() 

            if node:
                if node.left :
                    stackA.append(node.left) 
                if node.right:
                    stackB.append(node.right)
            
            print('delete ', node.val, end=' ')
            node.left = None
            node.right = None 
            del(node)


        print('delete ', self.root.val, )
        del(self.root)

        self.root = None 
        self.right = None 
        self.left = None 
    
    def is_valid(self):
        histo = {}

        if self.root == None:
            return None 
        
        q = [self.root]

        while q:

            node = q.pop(0)
            res = re.compile(r'0x.+[^\>]').search(str(node))  # match character class 
            key = 'addr_' + str(node)[res.span()[0] + 2 : res.span()[1]]

            if key not in  histo :
                histo[key] = 0
                
            histo[key] += 1

            if histo[key] > 1:
                return False 

            if node.left:
                if not (node.left.val < node.val):
                    return False 
                q.append(node.left)  
            
            if node.right:
                if not (node.right.val >= node.val ):
                    return False 
                q.append(node.right)
        
        return True 

    
    def add_without_dupes(self, val):
        prev = None 
        node = self.root 

        if node == None:
            self.root = BTNode(val)
        else:
            while node:

                if node.val == val:
                    return False 

                if node.left:
                    if val < node.val: 
                        node = node.left 
                        continue
                if node.right :
                    if val > node.val:
                        node = node.right 
                        continue 
                if node == None:
                    if val < prev.val:
                        prev.left = BTNode(val)
                        prev.left.parent = prev
                    if val > prev.val:
                        prev.right = BTNode(val)
                        prev.right.parent = prev 
                    break 
        return True 


    def val_before(self, val):
        node = self.root 

        if node == None:
            return None 
        
        while node:

            if node.val == val:
                if node.parent:
                    return node.parent.val 
                else:
                    return None 
            
            if node.right == None and node.left == None:
                if node.parent:
                    return node.parent.val 
                else:
                    return node.val 
            
            if node.parent:
                if val > node.val and val < node.parent.val:
                    return None 
            
            if node.parent:
                if val > node.parent.val and val < node.val:
                    return None
            
            
            
            if node.left:
                if val < node.val:
                    node = node.left 
                    continue
            
            if node.right:
                if val > node.val:
                    node = node.right 
                    continue
                
        return None 
        
    def val_after(self, val):
        node = self.root

        if node == None:
            return None 
        
        while node:

            if node.val == val:
                
                if node.right:
                    return node.right.val 
                else:
                    return None 
            
            if node.right == None and node.left == None:
                return None 
            
            if node.left:
                if val > node.left.val and val < node.val:
                    return node.val
                
                if val < node.val:
                    node = node.left 
                    continue 

            if node.right:
                if val < node.right.val and val > node.val:
                    return node.right.val
                
                if val > node.val:
                    node = node.right 
                    continue 

    def closest_value(self, val):
        class closest_node:
            def __init__(self, node):
                self.bst_node = node 
                self.path = []
        
        def clone(parent):
            c_node = closest_node(parent)
            c_node.bst_node = parent.bst_node
            c_node.path = parent.path + []
            return c_node 
        
        if self.root == None:
            return None 
        
        queue = [closest_node(self.root)]
        
        delta = None 

        while queue:
            
            node = queue.pop(0) 

            if node.bst_node.val == val:
                return node.bst_node.val
            
            if delta == None:
                delta = abs(val - node.bst_node.val)
            elif abs(val - node.bst_node.val) < delta:
                delta = abs(val - node.bst_node.val)
                
            if node.bst_node.right:
                
                if val > node.bst_node.val :
                    new_node = clone(node)
                    new_node.path += [node]
                    new_node.bst_node = new_node.bst_node.right 

                    if abs(val - node.bst_node.right.val) < delta:
                        queue.append(new_node)
            
            if node.bst_node.left:
                if val < node.bst_node.val:
                    new_node = clone(node)
                    new_node.path += [node]
                    new_node.bst_node = new_node.bst_node.left 
                    if abs(val - new_node.bst_node.left.val) < delta:
                        queue.append(new_node)  
        
        return node.bst_node.val

    def tree_path_sums (self):
        class sum_node:
            def __init__(self, node):
                self.path = [] 
                self.bst_node = node
                self.at_leaf = False 
        
        def clone(parent):
            c_node = sum_node(parent)
            c_node.path = parent.path +  []
            c_node.bst_node = parent.bst_node 
            return c_node 

        if self.root ==  None:
            return None 
        
        q = [ sum_node(self.root) ]

        paths = []
        
        while q:

            node = q.pop(0)

            if node:    

                if node.at_leaf:
                    paths.append( list(map( lambda node_: node_.bst_node.val ,  node.path) ))
                    continue

                if node.bst_node.left:
                    new_node = clone (node)
                    new_node.path += [node]
                    new_node.bst_node = new_node.bst_node.left
                    q.append(new_node)
                                    
                if node.bst_node.right:
                    new_node = clone (node)
                    new_node.path += [node]
                    new_node.bst_node = new_node.bst_node.right
                    q.append(new_node)

                # left node  or non full nodes 
                if node.bst_node.right == None and node.bst_node.left == None   or node.bst_node.right == None and node.bst_node.left or node.bst_node.right and node.bst_node.left == None :
                    new_node = clone(node) 
                    new_node.path += [node]
                    new_node.at_leaf = True 
                    q.append(new_node)

        return paths 

bst = BST() 
bst.add(22)
bst.add(22)
bst.add(18)
bst.add(23)
bst.add(23)

print(bst.root.val)   # 22
print(bst.root.right.val)  # 22
print(bst.root.right.right)  # None 
print(bst.root.right.left)  # None 

print('{}'.format(bst.contains(18)))
print('{}'.format(bst.contains(17)))
print('{}'.format(bst.contains(22)))
print('{} {}'.format('max', bst.max()))
print('{} {}'.format('min', bst.min()))
print('{} {}'.format('size', bst.size()))
print('{} {}'.format('is empty?', bst.is_empty()))
print('{} {}'.format('height?', bst.height()))
print('{} {}'.format('is balaned?', bst.is_balanced()))

#utility function to help review list of values in tree 
def array_to_bst(arr):
    bst = BST() 

    while len(arr):
        mid = len(arr) // 2

        # odd casee 
        if len(arr) % 2 == 1:
            mid + 1
            bst.add(arr[mid])
            arr = arr[0: mid] + arr[mid + 1 : :]
        # even 
        else:
            bst.add(arr[mid - 1])
            bst.add(arr[mid])
            arr = arr[0: mid - 1] + arr[mid + 1 : :]
    return bst 

arr = [1,2,3,4,5,6,6] 
tree_ = array_to_bst(arr)

print('{} {}'.format('root', tree_.root.val))  #3
print('{} {} '.format( 'right' , tree_.root.right.val))  #4
print('{} {} '.format('right right',tree_.root.right.right.val)) # 5
print('{} {} '.format( 'left', tree_.root.left.val)) # 2
print('{} {} '.format('left left', tree_.root.left.left.val)) # 1

print('min_height -  {} jump units'.format( tree_.min_height())) 

def closest_common_ancestor(bst, val_1, val_2):

    def get_path(bst, val, path ):
        node = bst.root 
        while node:
            path.append(node)
            if node.left and val < node.val:
                node = node.left 
            elif node.right and val > node.val:
                node = node.right 
            else:
                node = None 
    
    paths = [
        [],
        []
    ]

    get_path(bst, val_1, paths[0])
    get_path(bst, val_2, paths[1])

    # pop off path_1 until finding a match in path_0 list
    while paths[1]:
        node_1 = paths[1].pop() 
        # search path 0
        for node_0 in paths[0]:
            if node_0 == node_1:
                return node_0.val
    return None 

arr = [0,1,1.2,2,3,4,5] 
tree_ = array_to_bst(arr)
low = 0
high = 1.1
print('{} {}'.format('closest ancestor val', closest_common_ancestor(tree_ , low , high )))

# order the node 
def bst_to_array(bst):
    class search_node :
        def __init__(self, parent = None):
            self.bst_node = parent
            self.has_eval_left = False 
    
    stack = [search_node(bst.root)]
    result = [] 

    while stack:
        s_node = stack.pop() 

        if s_node.bst_node.left and s_node.has_eval_left == False:
            s_node.has_eval_left = True 
            stack.append(s_node)

            new_node = search_node(s_node.bst_node.left)
            stack.append(new_node)
            continue 
        

        result.append(s_node.bst_node.val)


        if s_node.bst_node.right:
            new_node = search_node(s_node.bst_node.right)
            stack.append(new_node)



    return result 

arr = [0,1,1.2,2,3,4,5] 
bst_tree = array_to_bst(arr)
print('{}'.format(bst_to_array(bst_tree))) 

# array return can be used to reproduce tree 
def bst_pre_order(bst):
    class search_node:
        def __init__(self, parent = None ):
            self.bst_node = parent 
    stack = []
    result = []

    if bst.root == None:
        return result 
    
    stack.append(search_node(bst.root))

    while stack:
        node = stack.pop() 

        if node:
            result +=  [node.bst_node.val]

            if node.bst_node.right: 
                new_node = search_node(node.bst_node.right)
                stack.append(new_node)

            if node.bst_node.left:
                new_node = search_node(node.bst_node.left)
                stack.append(new_node)     
    return result 

arr = [0,1,1.2,2,3,4,5] 
bst_tree = array_to_bst(arr)
print('{}'.format(bst_pre_order(bst_tree))) 


def bst_post_order(bst):

    class search_node:
        def __init__(self, parent = None) :
            self.bst_node = parent 
            self.eval_left = False 
            self.eval_right = False 

    stack = []
    result = [] 

    if bst.root == None: 
        return result 
    
    stack.append(search_node(bst.root))

    while stack:
        
        node = stack.pop()

        if node:

            if node.bst_node.left == None:
                node.eval_left = True 

            if node.bst_node.right == None:
                node.eval_right = True 

            if node.bst_node.left and node.eval_left == False :
                node.eval_left = True 
                stack.append(node)
                new_node = search_node(node.bst_node.left)
                stack.append(new_node)
                continue 

            elif node.bst_node.right and node.eval_right == False :
                node.eval_right = True 
                stack.append(node)
                new_node = search_node(node.bst_node.right)
                stack.append(new_node)
                continue 
            
            if (node.bst_node.left  == None and node.bst_node.right == None) or ( node.eval_right == True and node.eval_left == True ) :
                result.append(node.bst_node.val)
                
    return result

arr = [0,1,1.2,2,3,4,5] 
bst_tree = array_to_bst(arr)
print('{}'.format(bst_post_order(bst_tree))) 

# fun using path discovery

# remove root 
arr = [0,1,1.2,2,3,4,5] 
bst_tree = array_to_bst(arr)
bst_tree.remove(2)
print('Removed root value of 2, expect 1.2 ---- Solution = {}'.format(bst_tree.root.val))

# remove root 
arr = [0,1,1.2,2,3,4,5] 
bst_tree = array_to_bst(arr)
bst_tree.remove(1.2)
bst_tree.remove(2)
bst_tree.remove(3)
bst_tree.remove(4)
bst_tree.remove(4)
bst_tree.remove(5)

print('Removed value of 1.2 =  1 value was promoted {}'.format(bst_tree.root.left.val))

# remove root 
arr = [0,1,1.2,2,3,4,5] 
bst_tree = array_to_bst(arr)
# print('Removed all {}', bst_tree.remove_all())
print('is valid  {}', bst_tree.is_valid())


#traverse_reverse_in_order 
def traverse_reverse_in_order ( bst):
    class search_node:
        def __init__(self, parent):
            self.right_eval = False 
            self.bst_node = parent
    
    if bst.root == None:
        return None 
    stack = [search_node(bst.root)]
    result = [] 
    while stack:
        node = stack.pop()
        
        
        if node.right_eval == False :
            if node.bst_node.right:
                node.right_eval = True 
                stack.append(node)
                new_node = search_node(node.bst_node.right)
                stack.append(new_node)
                continue 
        
        result.append(node.bst_node.val)

        if node.bst_node.left:
            new_node = search_node(node.bst_node.left)
            stack.append(new_node)
    
    return result

# remove root 
arr = [0,1,1.2,2,3,4,5] 
bst_tree = array_to_bst(arr)
# print('Removed all {}', bst_tree.remove_all())
print('{}', traverse_reverse_in_order(bst_tree) )
print('{}', bst_tree.val_after(0.3) )
print('{}'.format( bst_tree.closest_value(29) ) )

print('{}'.format( bst_tree.tree_path_sums() ) )


def left_side_binary(bst):
    
    class buffer_node :
        def __init__(self, node):
            self.bst_node = node
            self.path = [] 
            self.is_leaf = False 
    
    def clone(bt_node):
        c_node = buffer_node(bt_node)
        c_node.path = node.path + []
        c_node.is_leaf = node.is_leaf 
        return c_node
    
    stackA = []
    stackB = []
    paths = [] 
    values_seen_on_left = []
    if bst.root == None:
        return None 
    
    stackA = [ buffer_node(bst.root) ]

    while stackA or stackB :
        
        if stackA :
            node = stackA.pop()
        
        elif stackB :
            node = stackB.pop()

        if node:

            if node.is_leaf:
                paths.append(  list(map( lambda node_: node_.bst_node.val,   node.path ) )  )
                continue 

            if node.bst_node.left:
                new_node = clone(node.bst_node.left)
                new_node.path += [node]
                stackA.append(new_node)

            if node.bst_node.right:
                new_node = clone(node.bst_node.right)
                new_node.path += [node]
                stackB.append(new_node)

            if node.bst_node.right == None and node.bst_node.left == None :
                new_node = clone(None)
                new_node.is_leaf = True 
                new_node.path += [node]
                stackA.append(new_node)
                continue 

    
    start = 0
    for array_path in paths:
        for number_seen in array_path[start : :] :
            values_seen_on_left.append(number_seen)
        start = len(array_path)

    return values_seen_on_left

arr = [100, 90, 125, 200, 300, 400, 80, 93, 91]
tree = BST()
for num in arr:
    tree.add(num)
print('{}'.format(left_side_binary(tree)))