class Node:
    def __init__(self, k):
        self.key = k
        self.parent = None
        self.left = None
        self.right = None
        
def in_order_walk (t):
    if t != None:
        in_order_walk (t.left)
        print (t.key)
        in_order_walk (t.right)

def reverse_order_walk (t):
    if t != None:
        in_order_walk (t.right)
        print (t.key)
        in_order_walk (t.left)

def pre_order_walk (t):
    if t != None:
        print (t.key)
        in_order_walk (t.left)
        in_order_walk (t.right)

def post_order_walk (t):
    if t != None:
        in_order_walk (t.left)
        in_order_walk (t.right)
        print (t.key)

def tree_min (t):
    if t == None:
        return None
    while t.left != None:
        t = t.left
    return t

def tree_min_key (t):
    if t == None:
        return None
    while t.left != None:
        t = t.left
    return t.key

def tree_max_key (t):
    if t == None:
        return None
    while t.right != None:
        t = t.right
    return t.key

def tree_search_r (t, k):
    if t == None:
        return False
    if k < t.key:
        return tree_search_r (t.left, k)
    elif k > t.key:
        return tree_search_r (t.right, k)
    else:
        return True

def tree_search (t, k):
    # True iff BST rooted at t contains key k, otherwise False
    while t != None:
        if t.key == k:
            return True
        if k < t.key:
            t = t.left
        else:
            t = t.right
    return False
    
def tree_insert_r (t, k):
    # return the root of the tree we obtain from inserting a new node
    # with key k into tree t
    if t == None:
        return Node (k)
    if k <= t.key:
        # recurse with t.left
        new_root = tree_insert_r (t.left, k)
        if new_root != t.left:
            t.left = new_root
            t.left.parent = t
    else:
        t.right = tree_insert_r (t.right, k)
        t.right.parent = t
    return t

def tree_insert (t, k):
    # return the root of the tree we obtain from inserting a new node
    # with key k into tree t
    if t == None:
        return Node(k)
    p = t
    while True:
        if k <= p.key:
            if p.left == None:
                p.left = Node(k)
                p.left.parent = p
                return t
            p = p.left
        else:
            if p.right == None:
                p.right = Node(k)
                p.right.parent = p
                return t
            p = p.right

def tree_successor (x):
    if x == None:
        return None
    if x.right != None:
        return tree_min (x.right)
    while x.parent != None:
        if x == x.parent.left:
            return x.parent
        x = x.parent
    return None

def tree_predecessor (x):
    if x == None:
        return None
    if x.left != None:
        return tree_max (x.left)
    while x.parent != None:
        if x == x.parent.right:
            return x.parent
        x = x.parent
    return None