Problem:

Binary Search Tree III

Write a program which performs the following operations to a binary search tree $T$ by adding delete operation to B: Binary Search Tree II.

  
insert  $k$: Insert a node containing $k$ as key into $T$.

  
find $k$: Report whether $T$ has a node containing $k$. 

  
delete $k$: Delete a node containing $k$.

  
print: Print the keys of the binary search tree by inorder tree walk and  preorder tree walk respectively.

The operation delete $k$ for deleting a given node $z$ containing key $k$ from $T$ can be implemented by an algorithm which considers the following cases:

 If $z$ has no children, we modify its parent $z.p$ to replace $z$ with NIL as its child (delete $z$).

 If $z$ has only a single child, we "splice out" $z$ by making a new link between its child and its parent.

 If $z$ has two children, we splice out $z$'s successor $y$ and replace $z$'s key with $y$'s key.

Input

   In the first line, the number of operations $m$ is given. In the following $m$ lines, operations represented by insert $k$, find $k$, delete $k$ or print are given.

Output

For each find $k$ operation, print "yes" if $T$ has a node containing $k$, "no" if not.

  In addition, for each print operation, print a list of keys obtained by inorder tree walk and preorder tree walk in a line respectively. Put a space character before each key

Constraints

   
The number of operations $\leq 500,000$

The number of print operations $\leq 10$.

  
$-2,000,000,000 \leq key \leq 2,000,000,000$

  
The height of the binary tree does not exceed 100 if you employ the above pseudo code.

The keys in the binary search tree are all different.

Sample Input 1

18
insert 8
insert 2
insert 3
insert 7
insert 22
insert 1
find 1
find 2
find 3
find 4
find 5
find 6
find 7
find 8
print
delete 3
delete 7
print

Sample Output 1

yes
yes
yes
no
no
no
yes
yes
 1 2 3 7 8 22
 8 2 1 3 7 22
 1 2 8 22
 8 2 1 22

Reference

Introduction to Algorithms, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. The MIT Press.



Sample input:
18
insert 8
insert 2
insert 3
insert 7
insert 22
insert 1
find 1
find 2
find 3
find 4
find 5
find 6
find 7
find 8
print
delete 3
delete 7
print


Sample output:
yes
yes
yes
no
no
no
yes
yes
 1 2 3 7 8 22
 8 2 1 3 7 22
 1 2 8 22
 8 2 1 22

Submission status: Accepted

Solution code:
import sys

class Node:
    __slots__ = ['key', 'left', 'right']
    def __init__(self, key):
        self.key = key
        self.left = self.right = None

root = None

def insert(key):
    global root
    x, y = root, None
    while x: x, y = x.left if key < x.key else x.right, x
    if y is None: root = Node(key)
    elif key < y.key: y.left = Node(key)
    else: y.right = Node(key)

def find(target):
    result = root
    while result and target != result.key:
        result = result.left if target < result.key else result.right
    return result is None

def delete(target):
    def remove_node(p, c, a):
        if p.left == c: p.left = a
        else: p.right = a
    p, c = None, root
    while c.key != target: p, c = c, c.left if target < c.key else c.right
    if c.left is None:
        remove_node(p, c, c.right)
    elif c.right is None:
        remove_node(p, c, c.left)
    elif c.right.left is None:
        c.right.left = c.left
        remove_node(p, c, c.right)
    else:
        g = c.right
        while g.left.left: g = g.left
        c.key = g.left.key
        g.left = g.left.right

def inorder(node):
    return inorder(node.left) + f' {node.key}' + inorder(node.right) if node else ''
def preorder(node):
    return f' {node.key}' + preorder(node.left) + preorder(node.right) if node else ''

input()
for e in sys.stdin:
    if e[0] == 'i': insert(int(e[7:]))
    elif e[0] == 'd': delete(int(e[7:]))
    elif e[0] == 'f': print(['yes','no'][find(int(e[5:]))])
    else: print(inorder(root)); print(preorder(root))

Submission status: Accepted

Solution code:
import collections
sent = None

def insert(hoge, new_node, root):
    parent_maybe = sent
    now_looking = root
    hoge[new_node]['node_id'] = new_node
    while now_looking != sent:
        parent_maybe = now_looking
        if new_node < hoge[now_looking]['node_id']:
            now_looking = hoge[now_looking]['left']
        else:
            now_looking = hoge[now_looking]['right']
    hoge[new_node]['parent'] = parent_maybe
    
    if parent_maybe == sent:
        root = new_node
        hoge[new_node]['parent'] = sent
        hoge[new_node]['left'] = sent
        hoge[new_node]['right'] = sent
    elif new_node < hoge[parent_maybe]['node_id']:
        hoge[parent_maybe]['left'] = new_node
        hoge[new_node]['left'] = sent
        hoge[new_node]['right'] = sent
    else:
        hoge[parent_maybe]['right'] = new_node
        hoge[new_node]['left'] = sent
        hoge[new_node]['right'] =sent
    
    return root
    
def inorder(node_id):
    if node_id == sent:
        return None
    inorder(hoge[node_id]['left'])
    print(' {}'.format(node_id), end='')
    inorder(hoge[node_id]['right'])

def preorder(node_id):
    if node_id == sent:
        return None
    print(' {}'.format(node_id), end='')
    preorder(hoge[node_id]['left'])
    preorder(hoge[node_id]['right'])
    
    
def getTree(root):
    inorder(root)
    print()
    preorder(root)
    print()
    
def searchNode(hoge, num, node_id):
    if node_id == sent:
        return 'no'
    
    if num == node_id:
        return 'yes'
    elif num < node_id:
        return searchNode(hoge, num, hoge[node_id]['left'])
    elif num > node_id:
        return searchNode(hoge, num, hoge[node_id]['right'])

def deleteNode(hoge, node_id):
    left_child = hoge[node_id]['left']
    right_child = hoge[node_id]['right']
    parent = hoge[node_id]['parent']
    if left_child == sent and right_child == sent:
        if hoge[parent]['left'] == node_id:
            hoge[parent]['left'] = sent
        else:
            hoge[parent]['right'] = sent
    elif left_child == sent and right_child != sent:
        if hoge[parent]['left'] == node_id:
            hoge[parent]['left'] = right_child
        else:
            hoge[parent]['right'] = right_child 
        hoge[right_child]['parent'] = parent
    elif right_child == sent and left_child != sent:
        if hoge[parent]['left'] == node_id:
            hoge[parent]['left'] = left_child
        else:
            hoge[parent]['right'] = left_child
        hoge[left_child]['parent'] = parent
    else:
        min_node = getMin(hoge, hoge[node_id]['right'])
        min_parent = hoge[min_node]['parent']
        if hoge[min_node]['right'] == sent:
            flag = True
        else:
            flag = False
        hoge[left_child]['parent'] = min_node
        hoge[right_child]['parent'] = min_node
        hoge[min_node]['left'] = left_child
        if min_node != right_child:
            hoge[min_node]['right'] = right_child
        hoge[min_node]['parent'] = parent
        if hoge[parent]['left'] == node_id:
            hoge[parent]['left'] = min_node
        else:
            hoge[parent]['right'] = min_node
            
        if flag:
            hoge[min_parent]['left'] = sent
        else:
            min_node_rchild = hoge[min_node]['right']
            hoge[min_parent]['left'] = min_node_rchild
            hoge[min_node_rchild]['parent'] = min_parent
    del hoge[node_id]
        
def getMin(hoge, node_id):
    while hoge[node_id]['left'] != sent:
        node_id = hoge[node_id]['left']
    return node_id

if __name__ == '__main__':
    num = int(input())
    hoge = collections.defaultdict(dict)
    root = sent
    for _ in range(num):
        command = input()
        if command.split()[0] == 'insert':
            root = insert(hoge, int(command.split()[1]), root)
        elif command.split()[0] == 'find':
            print(searchNode(hoge, int(command.split()[1]), root))
        elif command.split()[0] == 'delete':
            deleteNode(hoge, int(command.split()[1]))
        else:
            getTree(root)

Submission status: Accepted

Solution code:
class Tree():
    def __init__(self):
        self.root = None
    def insert(self, key):
        z = Node(key)
        y = None
        x = self.root
        while x:
            y = x
            if z.key < x.key:
                x = x.left
            else:
                x = x.right
        z.parent = y
        if y == None:
            self.root = z
        elif z.key < y.key:
            y.left = z
        else:
            y.right = z

    def print(self):
        print('', ' '.join(map(str, self.root.inwalk())))
        print('', ' '.join(map(str, self.root.prewalk())))

    def find(self, x, k):
        while x != None and k != x.key:
            if k < x.key:
                x = x.left
            else:
                x = x.right
        return x

    def delete(self, k):
        z = self.find(tree.root, k)
        y = self.successor(z) if z.left and z.right else z
        x = y.left if y.left else y.right

        if x:
            x.parent = y.parent
        if y.parent == None:
            self.root = x
        elif y == y.parent.left:
            y.parent.left = x
        else:
            y.parent.right = x
        if y != z:
            z.key = y.key

    def successor(self, x):
        if x.right:
            return self.minimum(x.right)
        y = x.parent
        while y and x == y.right:
            x = y
            y = y.parent
        return y

    def minimum(self, x):
        while x.left:
            x = x.left
        return x

class Node():
    def __init__(self, key):
        self.key = key
        self.parent = self.left = self.right = None

    def prewalk(self):
        ret = [self.key]
        if self.left:
            ret += self.left.prewalk()
        if self.right:
            ret += self.right.prewalk()
        return ret

    def inwalk(self):
        ret = []
        if self.left:
            ret += self.left.inwalk()
        ret += [self.key]
        if self.right:
            ret += self.right.inwalk()
        return ret

tree = Tree()
n = int(input())
for i in range(n):
    com = input().split()
    if com[0] == "insert":
        tree.insert(int(com[1]))
    elif com[0] == "find":
        ans = tree.find(tree.root, int(com[1]))
        if ans != None:
            print("yes")
        else:
            print("no")
    elif com[0] == "delete":
        tree.delete(int(com[1]))
    else:
        tree.print()

Submission status: Accepted

Solution code:
class Tree():
    def __init__(self):
        self.root = None
    def insert(self, key):
        z = Node(key)
        y = None
        x = self.root
        while x:
            y = x
            if z.key < x.key:
                x = x.left
            else:
                x = x.right
        z.parent = y
        if y == None:
            self.root = z
        elif z.key < y.key:
            y.left = z
        else:
            y.right = z

    def print(self):
        print('', ' '.join(map(str, self.root.inwalk())))
        print('', ' '.join(map(str, self.root.prewalk())))

    def find(self, x, k):
        while x != None and k != x.key:
            if k < x.key:
                x = x.left
            else:
                x = x.right
        return x

    def delete(self, k):
        z = self.find(tree.root, k)
        y = self.successor(z) if z.left and z.right else z
        x = y.left if y.left else y.right

        if x:
            x.parent = y.parent
        if y.parent == None:
            self.root = x
        elif y == y.parent.left:
            y.parent.left = x
        else:
            y.parent.right = x
        if y != z:
            z.key = y.key

    def successor(self, x):
        if x.right:
            return self.minimum(x.right)

    def minimum(self, x):
        while x.left:
            x = x.left
        return x

class Node():
    def __init__(self, key):
        self.key = key
        self.parent = self.left = self.right = None

    def prewalk(self):
        ret = [self.key]
        if self.left:
            ret += self.left.prewalk()
        if self.right:
            ret += self.right.prewalk()
        return ret

    def inwalk(self):
        ret = []
        if self.left:
            ret += self.left.inwalk()
        ret += [self.key]
        if self.right:
            ret += self.right.inwalk()
        return ret

tree = Tree()
n = int(input())
for i in range(n):
    com = input().split()
    if com[0] == "insert":
        tree.insert(int(com[1]))
    elif com[0] == "find":
        ans = tree.find(tree.root, int(com[1]))
        if ans != None:
            print("yes")
        else:
            print("no")
    elif com[0] == "delete":
        tree.delete(int(com[1]))
    else:
        tree.print()

Submission status: Accepted

Solution code:
class Tree():
    def __init__(self):
        self.root = None
    def insert(self, key):
        z = Node(key)
        y = None
        x = self.root
        while x:
            y = x
            if z.key < x.key:
                x = x.left
            else:
                x = x.right
        z.parent = y
        if y == None:
            self.root = z
        elif z.key < y.key:
            y.left = z
        else:
            y.right = z

    def print(self):
        print('', ' '.join(map(str, self.root.inwalk())))
        print('', ' '.join(map(str, self.root.prewalk())))

    def find(self, x, k):
        while x != None and k != x.key:
            if k < x.key:
                x = x.left
            else:
                x = x.right
        return x

    def delete(self, k):
        z = self.find(tree.root, k)
        y = self.minimum(z.right) if z.left and z.right else z
        x = y.left if y.left else y.right

        if x:
            x.parent = y.parent
        if y.parent == None:
            self.root = x
        elif y == y.parent.left:
            y.parent.left = x
        else:
            y.parent.right = x
        if y != z:
            z.key = y.key

    def minimum(self, x):
        while x.left:
            x = x.left
        return x

class Node():
    def __init__(self, key):
        self.key = key
        self.parent = self.left = self.right = None

    def prewalk(self):
        ret = [self.key]
        if self.left:
            ret += self.left.prewalk()
        if self.right:
            ret += self.right.prewalk()
        return ret

    def inwalk(self):
        ret = []
        if self.left:
            ret += self.left.inwalk()
        ret += [self.key]
        if self.right:
            ret += self.right.inwalk()
        return ret

tree = Tree()
n = int(input())
for i in range(n):
    com = input().split()
    if com[0] == "insert":
        tree.insert(int(com[1]))
    elif com[0] == "find":
        ans = tree.find(tree.root, int(com[1]))
        if ans != None:
            print("yes")
        else:
            print("no")
    elif com[0] == "delete":
        tree.delete(int(com[1]))
    else:
        tree.print()

Submission status: Accepted

Solution code:
import sys

class BinarySearchTree:
    class Node:
        __slots__ = ('value', 'left', 'right')

        def __init__(self, value):
            self.value = value
            self.left = None
            self.right = None

        def has_left(self):
            return self.left is not None

        def has_right(self):
            return self.right is not None

        def __str__(self):
            return str(self.value)

    def __init__(self):
        self.root = None

    def insert(self, value):
        if self.root is None:
            self.root = self.Node(value)
            return

        node = self.root
        while True:
            if node.value > value:
                if node.has_left():
                    node = node.left
                else:
                    node.left = self.Node(value)
                    break
            else:
                if node.has_right():
                    node = node.right
                else:
                    node.right = self.Node(value)
                    break

    def find(self, value):
        if self.root is None:
            return False

        node = self.root
        while True:
            if node.value > value:
                if node.has_left():
                    node = node.left
                else:
                    return False
            elif node.value < value:
                if node.has_right():
                    node = node.right
                else:
                    return False
            else:
                return True

    def delete(self, value):
        def _delete(node):
            if not node.has_left():
                right = node.right
                node.right = None
                return right
            elif not node.has_right():
                left = node.left
                node.left = None
                return left
            elif not node.right.has_left():
                right = node.right
                right.left = node.left
                node.left = None
                node.right = None
                return right
            else:
                repl = node.right
                while repl.has_left() and repl.left.has_left():
                    repl = repl.left

                left = repl.left
                node.value = left.value
                repl.left = left.right
                left.right = None
                return node

        if self.root is None:
            return
        elif self.root.value == value:
            self.root = _delete(self.root)
            return

        node = self.root
        while True:
            if node.value > value:
                if not node.has_left():
                    break
                if node.left.value == value:
                    node.left = _delete(node.left)
                    break
                else:
                    node = node.left
            elif node.value < value:
                if not node.has_right():
                    break
                if node.right.value == value:
                    node.right = _delete(node.right)
                    break
                else:
                    node = node.right
            else:
                raise Exception('should not reached')

    def preorder(self):
        def _preorder(node):
            yield node
            if node.has_left():
                yield from _preorder(node.left)
            if node.has_right():
                yield from _preorder(node.right)
        if self.root is not None:
            yield from _preorder(self.root)

    def inorder(self):
        def _inorder(node):
            if node.has_left():
                yield from _inorder(node.left)
            yield node
            if node.has_right():
                yield from _inorder(node.right)
        if self.root is not None:
            yield from _inorder(self.root)

    def postorder(self):
        def _postorder(node):
            if node.has_left():
                yield from _postorder(node.left)
            if node.has_right():
                yield from _postorder(node.right)
            yield node
        if self.root is not None:
            yield from _postorder(self.root)


def run():
    _ = int(input())
    tree = BinarySearchTree()

    for line in sys.stdin:
        if line.startswith('insert'):
            tree.insert(int(line[7:]))
        elif line.startswith('find'):
            if tree.find(int(line[5:])):
                print("yes")
            else:
                print("no")
        elif line.startswith('delete'):
            tree.delete(int(line[7:]))
        elif line.startswith('print'):
            print(' {}'.format(' '.join([str(n) for n in tree.inorder()])))
            print(' {}'.format(' '.join([str(n) for n in tree.preorder()])))
        else:
            raise ValueError('invalid command')


if __name__ == '__main__':
    run()

Submission status: Accepted

Solution code:
class Node:
    def __init__(self,key,left=None,right=None,parent=None):
        self.key = key
        self.left = left
        self.right = right
        self.parent = parent

root=None

#前序排序
def PreorderTreeWalk(u):
    if u == None:
        return
    print(" %d"%u.key,end='')
    PreorderTreeWalk(u.left)
    PreorderTreeWalk(u.right)

#中序排序
def InorderTreeWalk(u):
    if (u == None):
        return
    InorderTreeWalk(u.left)
    print(" %d"%u.key,end='')
    InorderTreeWalk(u.right)



def insert(value):
    global root
    
    y = None
    x = root
    z = Node(value)
 
    # 从根结点往下遍历
    while (x != None) :
        y = x
        # z 比 x 小， 则从x的左侧遍历
        # z 比 x 大， 则从x的右侧遍历
        if (z.key < x.key):
            x = x.left
        else:
            x = x.right
    

    z.parent = y

    #没有父结点的是root
    if (y == None): 
        root = z
    else: 
        # z 比 y 小， 则在y的左侧
        # z 比 y 大， 则在y的右侧
        if (z.key < y.key):
            y.left = z
        else:
            y.right = z
            
def find(u,value):
    while (u != None and u.key != value): 
        if (value < u.key):
            u = u.left;
        else:
            u = u.right;
    
    return u


# 树的最小值
def treeMinimum(x):
    while (x.left != None):
        x = x.left;
    return x


# case3如果同时具有左右子树。
#可以将结点x的左子树的最大值（也就是左子树一直往右孩子节点遍历即是最大值）
#或者右子树的最小值（也就是右子树一直往左孩子节点遍历即是最小值）替换x，然后拼接左子树或者右子树
#搜索后一个结点
def treeSuccessor(x) :
    if (x.right != None):
        return treeMinimum(x.right)

    y = x.parent;
    
    if x==y.left:
        return y
    else:
        while (y != None and x == y.right) :
            x = y
            x = y.parent
    
    return y


def treeDelete(z) :
        #x没有子结点，则将x结点删除即可 
        #如果x只有左子树或者只有右子树，则将子树拼接上父结点即可  
        # 确定要删除的结点
    if (z.left == None or z.right == None):
        y = z
    else:
        y = treeSuccessor(z)

    # 确定y的子结点x
    if (y.left != None):
        x = y.left
    else:
        x = y.right

    # 让子结点链接父结点
    if (x != None):
        x.parent = y.parent

    # 让父结点链接子结点
    if (y.parent == None):
        root = x
    else:
        if (y == y.parent.left):
            y.parent.left = x
        else:
            y.parent.right = x
    

    #case 3
    if (y != z):
        z.key = y.key;



n=int(input())
s=[]
for i in range(n):
    s=[x for x in input().split()]
    if s[0][0]=='i':
        insert(int(s[1]))    
    elif s[0][0]=='f':
        f = find(root,int(s[1]));
        if (f != None):
            print("yes")
        else:
            print("no")
    elif s[0][0]=='d':
            treeDelete(find(root, int(s[1])));
    else:
        InorderTreeWalk(root)
        print()
            
        PreorderTreeWalk(root)
        print()

Submission status: Accepted

Solution code:
class BinaryTreeNode():
    def __init__(self, val, parent=None, left=None, right=None):
        self.parent = parent
        self.left = None
        self.right = None
        self.val = val

    def get_child_num(self):
        num = 0
        if self.left != None: num += 1
        if self.right != None: num += 1
        return num

    def get_successor(self):
        x = self
        if x.right != None:
            return x.right.get_minimum()

        y = x.parent
        while y != None and x == y.right:
            x = y
            y = y.parent
        return y

    def get_minimum(self):
        x = self
        while x.left != None:
            x = x.left
        return x

class BinarySearchTree():
    def __init__(self):
        self.root = None

    def insert(self, val):
        y = None
        x = self.root
        while x != None:
            y = x
            if val < x.val:
                x = x.left
            else:
                x = x.right
        node = BinaryTreeNode(val=val, parent=y)

        if y == None:
            self.root = node
        elif node.val < y.val:
            y.left = node
        else:
            y.right = node

    def find(self, val):
        x = self.root
        while x != None:
            if x.val == val:
                return x
            elif x.val < val:
                x = x.right
            else:
                x = x.left
        return None

    def delete(self, val):
        z = self.find(val)
        if z == None: return

        y = None
        if z.get_child_num() < 2:
            y = z
        else:
            y = z.get_successor()

        x = None
        if y.left != None:
            x = y.left
        else:
            x = y.right

        if x != None:
            x.parent = y.parent

        if y.parent == None:
            self.root = x
        elif y == y.parent.left:
            y.parent.left = x
        else:
            y.parent.right = x

        if y != z:
            z.val = y.val

    def preorder(self):
        self.preorder_list = []
        self.preorder_bfs(self.root)
        return self.preorder_list

    def preorder_bfs(self, u):
        if u == None: return
        self.preorder_list.append(u.val)
        self.preorder_bfs(u.left)
        self.preorder_bfs(u.right)

    def inorder(self):
        self.inorder_list = []
        self.inorder_dfs(self.root)
        return self.inorder_list

    def inorder_dfs(self, u):
        if u == None: return
        self.inorder_dfs(u.left)
        self.inorder_list.append(u.val)
        self.inorder_dfs(u.right)

def print_elements(arr):
    print(' ' + ' '.join([str(item) for item in arr]))

m = int(input())
bst = BinarySearchTree()
for i in range(m):
    op = input()
    if op.startswith('insert'):
        num = int(op[7:])
        bst.insert(num)
    elif op.startswith('delete'):
        num = int(op[7:])
        bst.delete(num)
    elif op.startswith('find'):
        num = int(op[5:])
        if bst.find(num):
            print('yes')
        else:
            print('no')
    else:
        print_elements(bst.inorder())
        print_elements(bst.preorder())

Submission status: Accepted

Solution code:
class Tree:
    def __init__(self, orders):
        self.root = None
        for order in orders:
            if len(order) == 1:
                self.inorder_print()
                self.preorder_print()
            else:
                fchr = order[0][0]
                key = int(order[1])
                if fchr == 'f':
                    self.find(key)
                elif fchr == 'i':
                    self.insert(key)
                else:
                    self.delete(key)

    def insert(self, key):
        z = Node(key)
        y = None
        x = self.root
        while x:
            y = x
            if z.key < x.key:
                x = x.left
            else:
                x = x.right
        z.parent = y
        if not y:
            self.root = z
        elif z.key < y.key:
            y.left = z
        else:
            y.right = z

    def find(self, key):
        x = self.root
        while True:
            if key == x.key:
                print('yes')
                break
            elif key < x.key:
                if x.left:
                    x = x.left
                else:
                    print('no')
                    break
            else:
                if x.right:
                    x = x.right
                else:
                    print('no')
                    break

    def delete(self, key):
        z = self.root
        while z.key != key:
            if key < z.key:
                z = z.left
            else:
                z = z.right

        if not z.left or not z.right:
            y = z
        else:
            y = self.get_successor(z)

        if y.left:
            x = y.left
        else:
            x = y.right

        if x:
            x.parent = y.parent

        if not y.parent:
            self.root = x
        elif y == y.parent.left:
            y.parent.left = x
        else:
            y.parent.right = x

        if y != z:
            z.key = y.key

        del (y)

    def get_successor(self, x):
        if x.right:
            return self.get_minimum(x.right)

        y = x.parent
        while y and x == y.right:
            x = y
            y = y.parent
        return y

    def get_minimum(self, x):
        while x.left:
            x = x.left
        return x

    def inorder_print(self):
        self.root.inorder_print()
        print()

    def preorder_print(self):
        self.root.preorder_print()
        print()


class Node:
    def __init__(self, key):
        self.key = key
        self.parent = None
        self.left = None
        self.right = None

    def inorder_print(self):
        if self.left:
            self.left.inorder_print()
        print(' {}'.format(self.key), end='')
        if self.right:
            self.right.inorder_print()

    def preorder_print(self):
        print(' {}'.format(self.key), end='')
        if self.left:
            self.left.preorder_print()
        if self.right:
            self.right.preorder_print()


if __name__ == '__main__':
    import sys
    m = int(input())
    orders = [line.strip().split() for line in sys.stdin]
    Tree(orders)