Problem:

Binary Search Tree II

Write a program which performs the following operations to a binary search tree $T$ by adding the find operation to A: Binary Search Tree I.

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

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

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

Input

  In the first line, the number of operations $m$ is given. In the following $m$ lines, operations represented by insert $k$, find $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

10
insert 30
insert 88
insert 12
insert 1
insert 20
find 12
insert 17
insert 25
find 16
print

Sample Output 1

yes
no
 1 12 17 20 25 30 88
 30 12 1 20 17 25 88

Reference

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



Sample input:
10
insert 30
insert 88
insert 12
insert 1
insert 20
find 12
insert 17
insert 25
find 16
print


Sample output:
yes
no
 1 12 17 20 25 30 88
 30 12 1 20 17 25 88

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import random
import sys
import os


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

    def __str__(self):
        if self.root == None:
            return None
        else:
            return "TODO"

    def print_inorder(self):
        self.inorder_list = []
        self.__inorder(self.root)
        return self.inorder_list

    def __inorder(self, node):
        """
        :param node: Node
        :return:
        """
        if node is None:
            return
        else:
            self.__inorder(node.left)
            self.inorder_list.append(node.key)
            self.__inorder(node.right)

    def print_preorder(self):
        self.preorder_list = []
        self.__preorder(self.root)
        return self.preorder_list

    def __preorder(self, node):
        """
        :param node: Node
        :return:
        """
        if node is None:
            return
        else:
            self.preorder_list.append(node.key)
            self.__preorder(node.left)
            self.__preorder(node.right)

    def insert(self, node):
        """
        :param node: Node
        :return:
        """
        if self.root is None:
            self.root = node
        else:
            x = self.root
            parent_candidate = x

            while x is not None:
                parent_candidate = x
                if x.key > node.key:
                    x = x.left
                else:
                    x = x.right

            # child to parent link
            x = node
            x.parent = parent_candidate

            # parent to child link
            if x.key < x.parent.key:
                x.parent.left = x
            else:
                x.parent.right = x

    def find(self, value):
        """
        :param value:
        :rtype: Node
        :return:
        """
        x = self.root
        while x is not None and x.key != value:
            if x.key > value:
                x = x.left
            else:
                x = x.right
        return x

    def delete(self, value):
        found_node = self.find(value)
        if found_node is None:
            print("value is nothing")
        else:
            # has no child
            if found_node.is_leaf():
                # delete link from parent
                print(found_node.parent.left.key)
                print(found_node.key)

                if found_node.parent.left.key == found_node.key:
                    found_node.parent.left = None
                else:
                    found_node.parent.right = None
            else:
                # has one child
                if found_node.has_one_child():
                    one_child = found_node.get_one_child()

                    # change link to parent
                    one_child.parent = found_node.parent

                    # chagne link from parent
                    if found_node.parent.left == found_node:
                        found_node.parent.left = one_child
                    else:
                        found_node.parent.right = one_child

                # has two child
                else:
                    next_section_point = found_node.get_next_section_point()
                    # ?¬???????????????????????????????????????????????¬?????????????????????? p217
                    # ????????????
                    key = next_section_point.key
                    self.delete(next_section_point.key)
                    found_node.key = key


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

    def has_one_child(self):
        if self.left is None and self.right is not None:
            return True
        elif self.left is not None and self.right is None:
            return True
        else:
            return False

    def get_one_child(self):
        if not self.has_one_child():
            return None
        else:
            if self.left is not None:
                return self.left
            else:
                return self.right

    def get_next_section_point(self):
        """?¬??????????????????????"""

        # ????????????????????´???
        if self.right is not None:
            return self.right.get_minimum()
        # ???????????????????????´???????¬???????????????´?????????
        else:
            # ?
            return self.parent

    def is_leaf(self):
        if self.left is None and self.right is None:
            return True
        else:
            return False

    def get_minimum(self):
        if self.left is None:
            return self
        else:
            return self.left.get_minimum()

tree = Tree()
s = input()
n = int(s)
for _ in range(n):
    s = input()
    if 'insert' in s:
        value = int(s.split(" ")[-1])
        node = Node(value)
        tree.insert(node)

    if 'print' in s:
        in_list = tree.print_inorder()
        in_list = map(str, in_list)
        print(' ' + ' '.join(in_list))

        pre_list = tree.print_preorder()
        pre_list = map(str, pre_list)
        print(' ' + ' '.join(pre_list))

    if 'find' in s:
        value = int(s.split(" ")[-1])
        node = tree.find(value)
        if node is None:
            print('no')
        else:
            print('yes')

Submission status: Accepted

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

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

  def insert(self, z):
    y = None
    x = self.root
    while x != None:
      y = x
      if z.key < x.key:
        x = x.left
      else:
        x = x.right
    z.p = y

    if y is None:
      self.root = z
    elif z.key < y.key:
      y.left = z
    else:
      y.right = z

def print_inorder(node):
  if node is None: return
  print_inorder(node.left)
  print(" {}".format(node.key), end="")
  print_inorder(node.right)

def print_preorder(node):
  if node is None: return
  print(" {}".format(node.key), end="")
  print_preorder(node.left)
  print_preorder(node.right)

def find(node, key):
  if node is None: return False
  if node.key == key: return True
  if key < node.key:
    return find(node.left, key)
  else:
    return find(node.right, key)

T = BinarySearchTree()
for i in range(int(input())):
  params = input().split()
  if params[0] == "insert":
    T.insert(Node(int(params[1])))
  if params[0] == "find":
    if find(T.root, int(params[1])):
      print("yes")
    else:
      print("no")
  if params[0] == "print":
    print_inorder(T.root)
    print("")
    print_preorder(T.root)
    print("")

Submission status: Accepted

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

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

  def insert(self, z):
    y = None
    x = self.root
    while x != None:
      y = x
      if z.key < x.key:
        x = x.left
      else:
        x = x.right
    z.p = y

    if y is None:
      self.root = z
    elif z.key < y.key:
      y.left = z
    else:
      y.right = z

def print_inorder(node):
  if node is None: return
  print_inorder(node.left)
  print(" {}".format(node.key), end="")
  print_inorder(node.right)

def print_preorder(node):
  if node is None: return
  print(" {}".format(node.key), end="")
  print_preorder(node.left)
  print_preorder(node.right)

def find(node, key):
  while node:
    if node.key == key: return True
    if key < node.key:
      node = node.left
    else:
      node = node.right
  return False

T = BinarySearchTree()
for i in range(int(input())):
  params = input().split()
  if params[0] == "insert":
    T.insert(Node(int(params[1])))
  if params[0] == "find":
    if find(T.root, int(params[1])):
      print("yes")
    else:
      print("no")
  if params[0] == "print":
    print_inorder(T.root)
    print("")
    print_preorder(T.root)
    print("")

Submission status: Accepted

Solution code:
class Tree:
    def __init__(self):
        self.root = None

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

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

    def show(self):
        print(" ", end="")
        print(*list(map(str, self.root.inwalk())))
        print(" ", end="")
        print(*list(map(str, self.root.prewalk())))


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

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

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


tree = Tree()
n = int(input())
for i in range(n):
    cmd = list(input().split())
    if cmd[0] == 'insert':
        tree.insert(int(cmd[1]))
    elif cmd[0] == 'find':
        if tree.find(int(cmd[1])):
            print("yes")
        else:
            print("no")
    elif cmd[0] == 'print':
        tree.show()

Submission status: Accepted

Solution code:
#BinarySearchTree
class TreeNode():
    def __init__(self):
        self.key = None
        self.parent = None
        self.left = None
        self.right = None
    def inoder(self):
        r=[]
        if self.left:
            r += self.left.inoder()
        r += [self.key]
        if self.right:
            r += self.right.inoder()
        return r

    def preoder(self):
        r = [self.key]
        if self.left:
            r += self.left.preoder()
        if self.right:
            r += self.right.preoder()
        return r

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

    def insert(self, z):
        y = None
        x = self.root
        while x != None:
            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 show(self):
        x = self.root
        print(" " + " ".join(map(str, self.root.inoder())))
        print(" " + " ".join(map(str, self.root.preoder())))

    def find(self, key):
        currentNode = self.root
        while currentNode:
            if key == currentNode.key:
                return True
            else:
                if key < currentNode.key:
                    currentNode = currentNode.left
                else:
                    currentNode = currentNode.right
        return False


n = int(input())
Tree = BinaryTree()
for i in range(n):
    L = input().split()
    if L[0] == "insert":
        Node = TreeNode()
        Node.key = int(L[1])
        Tree.insert(Node)
    elif L[0] =="print":
        Tree.show()
    else:
        if Tree.find(int(L[1])):
            print("yes")
        else:
            print("no")

Submission status: Accepted

Solution code:
import sys

class Node:
    def __init__(self, x):
        self.data = x
        self.left = None
        self.right = None
    
    def insert(node, x):
        if node == None:
            return Node(x)
#==============================================================================
#         elif x == node.data:
#             return node
#==============================================================================
        elif x < node.data:
            node.left = Node.insert(node.left, x)
        else:
            node.right = Node.insert(node.right, x)
        return node
    
    def find(node, x):
        if node.data == x:
            return True
        elif node.left != None and node.data > x:
            return Node.find(node.left, x)
        elif node.right != None and node.data < x:
            return Node.find(node.right, x)
        else:
            return False
        
    def delete(node, x):
        if node.data == x:
            if (node.left == None) and (node.right == None):
                return None
            elif node.left == None:
                return node.right
            elif node.right == None:
                return node.left
            else:
                #????????????
                node.data = Node.serch_min(node.right)
                node.right = Node.delete_min(node.right)
                return node
        elif node.data > x:
            node.left =  Node.delete(node.left, x)
        else:
            node.right = Node.delete(node.right, x)
        return node
        
    def serch_min(node):
        if node.left != None:
            return Node.serch_min(node.left)
        else:
            return node.data
    
    def delete_min(node):
        if node.left == None:
            return node.right
        else:
            node.left = Node.delete_min(node.left)
            return node    
        
    def inorder_print(node):
        if node.left != None:
            Node.inorder_print(node.left)
        print("",node.data,  end="")
        if node.right != None:
            Node.inorder_print(node.right)
    def preorder_print(node):
        print("",node.data,  end="")
        if node.left != None:
            Node.preorder_print(node.left)
        if node.right != None:
            Node.preorder_print(node.right)
        
class BinaryTree:
    def __init__(self):
        self.root = None
    
    def insert(self, x):
        self.root = Node.insert(self.root, x)

    def find(self, x):
        if Node.find(self.root, x):
            print("yes")
        else:
            print("no")
            
    def delete(self, x):
        self.root = Node.delete(self.root, x)
        
    def print_tree(self):
        Node.inorder_print(self.root)
        print()
        Node.preorder_print(self.root)
        print()

def main():
    T = BinaryTree()
    m = int(sys.stdin.readline())
    for i in range(m):
        s = sys.stdin.readline().strip()
        if(s == "print"):
            T.print_tree()
        elif s.split()[0] == "find":
            T.find(int(s.split()[1]))
        elif s.split()[0] == "delete":
            T.delete(int(s.split()[1]))
        else:
            z = int(s.split()[1])
            T.insert(z)
        #print(s)
        #T.print_tree()

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

class Node:
    def __init__(self, x):
        self.data = x
        self.left = None
        self.right = None
    
    def insert(node, x):
        if node == None:
            return Node(x)
#==============================================================================
#         elif x == node.data:
#             return node
#==============================================================================
        elif x < node.data:
            node.left = Node.insert(node.left, x)
        else:
            node.right = Node.insert(node.right, x)
        return node
    
    def find(node, x):
        if node.data == x:
            return True
        elif node.left != None and node.data > x:
            return Node.find(node.left, x)
        elif node.right != None and node.data < x:
            return Node.find(node.right, x)
        else:
            return False
        
    def delete(node, x):
        if node.data == x:
            if (node.left == None) and (node.right == None):
                return None
            elif node.left == None:
                return node.right
            elif node.right == None:
                return node.left
            else:
                #????????????
                node.data = Node.serch_min(node.right)
                node.right = Node.delete_min(node.right)
                return node
        elif node.data > x:
            node.left =  Node.delete(node.left, x)
        else:
            node.right = Node.delete(node.right, x)
        return node
        
    def serch_min(node):
        if node.left != None:
            return Node.serch_min(node.left)
        else:
            return node.data
    
    def delete_min(node):
        if node.left == None:
            return node.right
        else:
            node.left = Node.delete_min(node.left)
            return node    
        
    def inorder_print(node):
#==============================================================================
#         if node.left != None:
#             Node.inorder_print(node.left)
#         print("",node.data,  end="")
#         if node.right != None:
#             Node.inorder_print(node.right)
#==============================================================================
        s = ""
        if node.left != None:
            s += Node.inorder_print(node.left)
        s += " " + str(node.data)
        if node.right != None:
            s += Node.inorder_print(node.right)
        return s
    def preorder_print(node):
#==============================================================================
#         print("",node.data,  end="")
#         if node.left != None:
#             Node.preorder_print(node.left)
#         if node.right != None:
#             Node.preorder_print(node.right)
#==============================================================================
        s = ""
        s += " " + str(node.data)
        if node.left != None:
            s += Node.preorder_print(node.left)    
        if node.right != None:
            s += Node.preorder_print(node.right)
        return s
class BinaryTree:
    def __init__(self):
        self.root = None
    
    def insert(self, x):
        self.root = Node.insert(self.root, x)

    def find(self, x):
        if Node.find(self.root, x):
            print("yes")
        else:
            print("no")
            
    def delete(self, x):
        self.root = Node.delete(self.root, x)
        
    def print_tree(self):
#==============================================================================
#         Node.inorder_print(self.root)
#         print()
#         Node.preorder_print(self.root)
#         print()
#==============================================================================
        s = Node.inorder_print(self.root)
        print(s)
        s = Node.preorder_print(self.root)
        print(s)
def main():
    T = BinaryTree()
    m = int(sys.stdin.readline())
    for i in range(m):
        s = sys.stdin.readline().strip()
        if(s == "print"):
            T.print_tree()
        elif s.split()[0] == "find":
            T.find(int(s.split()[1]))
        elif s.split()[0] == "delete":
            T.delete(int(s.split()[1]))
        else:
            z = int(s.split()[1])
            T.insert(z)
        #print(s)
        #T.print_tree()

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# coding=utf-8

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

    def insert(self, key):
        node = Node(key)
        flag = False

        if self.root == None:
            self.root = node
        else:
            search_node = self.root
            while search_node:
                final_node = search_node
                if final_node.key < key:
                    search_node = final_node.right
                    flag = 'right'
                else:
                    search_node = final_node.left
                    flag = 'left'
            node.parent = final_node
            if flag == 'right':
                final_node.right = node
            elif flag == 'left':
                final_node.left = node

    def tprint(self):
        self.root.inwalk()
        print()
        self.root.prewalk()
        print()

    def find(self, key):
        if self.root.find(key):
            print('yes')
        else:
            print('no')


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

    def prewalk(self):
        print(" " + str(self.key), end = "")
        if self.left:
            self.left.prewalk()
        if self.right:
            self.right.prewalk()

    def inwalk(self):
        if self.left:
            self.left.inwalk()
        print(' ' + str(self.key), end = "")
        if self.right:
            self.right.inwalk()

    def find(self, key):
        find_flag = False
        node = self

        while node != None:
            if key > node.key:
                node = node.right
            elif key < node.key:
                node = node.left
            elif key == node.key:
                find_flag = True
                break

        return find_flag


n = int(input())
tree = Tree()

for _ in range(n):
    order, *key = input().split()
    if order == 'insert':
        tree.insert(int(key[0]))

    elif order == 'find':
        tree.find(int(key[0]))

    elif order == 'print':
        tree.tprint()

Submission status: Accepted

Solution code:
import sys


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

    def preorder(self):
        nodeList = [self.key]
        if self.left:
            nodeList += self.left.preorder()
        if self.right:
            nodeList += self.right.preorder()
        return nodeList

    def inorder(self):
        nodeList = []
        if self.left:
            nodeList += self.left.inorder()
        nodeList += [self.key]
        if self.right:
            nodeList += self.right.inorder()
        return nodeList


class BinaryTree():
    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 is None:
            self.root = z
        elif z.key < y.key:
            y.left = z
        else:
            y.right = z

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

    def print(self):
        print(" " + " ".join(map(str, self.root.inorder())))
        print(" " + " ".join(map(str, self.root.preorder())))


if __name__ == "__main__":
    tree = BinaryTree()
    n = int(sys.stdin.readline())
    for inp in sys.stdin.readlines():
        inp = inp.split()
        if inp[0] == "insert":
            tree.insert(int(inp[1]))
        elif inp[0] == "find":
            if tree.find(int(inp[1])) is None:
                print("no")
            else:
                print("yes")
        else:
            tree.print()

Submission status: Accepted

Solution code:
import sys

def main():
    n = input()
    tree = MyBinaryTree(n)
    for i in range(n):
        cmd = map(str,raw_input().split())
        if cmd[0] == "insert":
            insert(tree,MyNode(int(cmd[1])))
        elif cmd[0] == "print":
            tree.inorder(tree.root)
            print ""
            tree.preorder(tree.root)
            print ""
        elif cmd[0] == "find":
            find(tree,int(cmd[1]))
    
    
class MyBinaryTree():
    def __init__(self,num_nodes):
        self.root = None

    def preorder(self,node):
        sys.stdout.write(" {}".format(node.key))
        l = node.left
        r = node.right
        if l is not None:
            self.preorder(l)
        if r is not None:
            self.preorder(r)    

    def inorder(self,node):
        l = node.left
        r = node.right
        if l is not None:
            self.inorder(l)
        sys.stdout.write(" {}".format(node.key))
        if r is not None:
            self.inorder(r)


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

    if y is None:
        T.root = z
    elif z.key < y.key:
        y.left = z
    else:
        y.right = z


def find(T,key):
    x = T.root
    while x is not None and key != x.key:
        if key < x.key:
            x = x.left
        else:
            x = x.right

    if x is not None:
        print "yes"
    else:
        print "no"

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

class Node:
    def __init__(self, value, p = None, l = None, r = None):
        self.key = value
        self.p = p
        self.left = l
        self.right = r

def getroot(x):
    if x.p != None:
        return getroot(x.p)
    return x

def preorder(x, A):
    if x == None:
        return
    A.append(x.key)
    preorder(x.left, A)
    preorder(x.right, A)

def inorder(x, A):
    if x == None:
        return
    inorder(x.left, A)
    A.append(x.key)
    inorder(x.right, A)

def postorder(x, A):
    if x == None:
        return
    postorder(x.left, A)
    postorder(x.right, A)
    A.append(x.key)

def ptree(root):
    pre = [""]
    ino = [""]
    preorder(root, pre)
    inorder(root, ino)
    print(" ".join(map(str,ino)))
    print(" ".join(map(str,pre)))

def find(value, root):
    if root == None:
        return "no"
    elif value < root.key:
        return find(value,root.left)
    elif value > root.key:
        return find(value,root.right)
    return "yes"

def insert(Tree, root, z):
    y = None # x ??????
    x = root  # 'T ??????'
    while x != None:
        y = x # ???????¨????
        if z.key < x.key:
            x = x.left # ?????????????§????
        else:
            x = x.right # ?????????????§????
    z.p = y

    Tree.append(z)
    if y == None: # T ???????????´???
        return z
    elif z.key < y.key:
        y.left = z # z ??? y ?????????????????????
    else:
        y.right = z # z ??? y ?????????????????????
    return root

def main():

    """ ????????? """
    num = int(input().strip())
    istr = sys.stdin.read()
    cmds = list(istr.splitlines())
    Tree = []
    root = None
    for i in range(num):
        cmd = cmds[i][0]
        if cmd == "i":
            n = Node(int(cmds[i][7:]))
            root = insert(Tree, root, n)
        elif cmd == "f":
            print(find(int(cmds[i][5:]),root))
        elif cmd == "p":
            ptree(root)
    

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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 preorder(self, node):
        print(" {}".format(node.key), end = "")
        if node.left:
            self.preorder(node.left)
        if node.right:
            self.preorder(node.right)
            
    def inorder(self, node):
        if node.left:
            self.inorder(node.left)
        print(" {}".format(node.key), end = "")
        if node.right:
            self.inorder(node.right)
            
    def find(self, key):
        node = self.root
        while node:
            if node.key == key:
                return 'yes'
            elif node.key > key:
                node = node.left
            else:
                node = node.right
        return 'no'
    
    def out(self):
        self.inorder(self.root)
        print('')
        self.preorder(self.root)
        print('')

tree = Tree()
N = int(input())
for _ in range(N):
    order = input().split()
    if order[0] == 'insert':
        tree.insert(int(order[1]))
    elif order[0] == 'find':
        print(tree.find(int(order[1])))
    else:
        tree.out()