ADA_l2x1

class Node:
    def __init__(self, val):
        self.l_child = None
        self.r_child = None
        self.parent = None
        self.data = val

    def __repr__(self):
        if hasattr(self, 'data'):
            return str(self.data)
        return "N/A, does not exist"

    def __str__(self):
        return "\t  " + str(self.data) + "\n\t / \\\n\t" + str(self.l_child.data) + "   " + str(self.r_child.data)

def binary_insert(root, node):
    if root is None:
        root = node
    else:
        if root.data > node.data: # insert on left side
            if root.l_child is None:
                root.l_child = node
            else:
                binary_insert(root.l_child, node)
        else: # insert on right side
            if root.r_child is None:
                root.r_child = node
            else:
                binary_insert(root.r_child, node)

def in_order_print(root):
    if not root:
        return
    in_order_print(root.l_child)
    print(root.data)
    in_order_print(root.r_child)

def pre_order_print(root):
    if not root:
        return
    print(root.data)
    pre_order_print(root.l_child)
    pre_order_print(root.r_child)

def height(root, h = 0):
    if not root:
        return h
    leftHeight = height(root.l_child, h + 1)
    rightHeight = height(root.r_child, h + 1)
    return max(leftHeight, rightHeight)

def search(root, key):
    if (root.data == key):
        return root
    if not root:
        return
    if (key < root.data):
        return search(root.l_child, key)
    else:
        return search(root.r_child, key)

def successor(root):
    if not root:
        return
    #print(root)
    if(root.r_child is None):
        return None
    successor = root.r_child

    while(successor.l_child):
        successor = successor.l_child

    return successor.data

root = Node(5)
binary_insert(root, Node(3))
binary_insert(root, Node(8))
binary_insert(root, Node(1))
in_order_print(root)
print(successor(root))