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.

Solution (Python):

import sys
sys.setrecursionlimit(100000)

def insert(k, node):
    if k < node:
        if tree[node]["left"] == None:
            tree[node]["left"] = k
            tree[k] = {"parent": node, "left": None, "right": None}
            return
        else:
            insert(k, tree[node]["left"])
    else:
        if tree[node]["right"] == None:
            tree[node]["right"] = k
            tree[k] = {"parent": node, "left": None, "right": None}
            return
        else:
            insert(k, tree[node]["right"])


def pre_order(n):
    result = []
    if n == None:
        return []
    result.append(str(n))
    result.extend(pre_order(tree[n]["left"]))
    result.extend(pre_order(tree[n]["right"]))
    
    return result


def in_order(n):
    result = []
    
    if n == None:
        return []

    result.extend(in_order(tree[n]["left"]))
    result.append(str(n))
    result.extend(in_order(tree[n]["right"]))
    
    return result

def find(k, node):
    while node != None and node != k:
        if k < node:
            node = tree[node]["left"]
        else:
            node = tree[node]["right"]

    return node


M = int(input())
root = None
while root == None:
    inp = [n for n in input().split()]
    if inp[0] == "print":
        print()
        print()
    else:
        root = int(inp[1])

tree = {root:{"parent": None, "left": None, "right": None}}

for i, _ in enumerate(range(M-1)):
    inp = [n for n in input().split()]
    if inp[0] == "print":
        in_text = ""
        pre_text = ""
        print(" " + " ".join(in_order(root)))
        print(" " + " ".join(pre_order(root)))
        
    elif inp[0] == "find":
        res = find(int(inp[1]), root)
        if res == None:
            print("no")
        else:
            print("yes")
    else:
        insert(int(inp[1]), root)

Solution (Python):
m = int(input())

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


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

    def getRoot(self):
        return self.root
    def setRoot(self, v):
        self.root = v

    def inorder(self, v=None):
        if v is None:
            v = self.root
        if v.left is not None:
            self.inorder(v.left)
        print(' ' + str(v.key), end='')
        if v.right is not None:
            self.inorder(v.right)
        
    def preorder(self, v=None):
        if v is None:
            v = self.root
        print(' ' + str(v.key), end='')
        if v.left is not None:
            self.preorder(v.left)
        if v.right is not None:
            self.preorder(v.right)

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

    if y is None:
        T.setRoot(z)
    elif z.key < y.key:
        y.left = z
    else:
        y.right = z

def find(T, k):
    x = T.getRoot()
    while x is not None:
        if x.key == k:
            print('yes')
            return
        elif x.key < k:
            x = x.right
        else:
            x = x.left
    print('no')


T = BinaryTree()

for i in range(m):
    inp = input().split()
    if inp[0] == 'print':
        T.inorder()
        print()
        T.preorder()
        print()
    elif inp[0] == 'find':
        find(T, int(inp[1]))
    else:
        v = Node(int(inp[1]), None, None)
        insert(T, v)

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


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

    def insert(self, key):
        root_node = self.root
        insert_node = Node(key)
        parent_node = None

        while root_node:
            parent_node = root_node
            if insert_node.key < root_node.key:
                root_node = root_node.left
            else:
                root_node = root_node.right

        insert_node.parent = parent_node

        if parent_node is None:
            self.root = insert_node
        elif insert_node.key < parent_node.key:
            parent_node.left = insert_node
        else:
            parent_node.right = insert_node

    def find(self, key):
        root_node = self.root

        while root_node:
            if root_node.key == key:
                print('yes')
                return 0
            elif root_node.key < key:
                root_node = root_node.right
            else:
                root_node = root_node.left

        print('no')


    def show_preorder(self, node):
        node_list = []

        node_list.append(node.key)
        if node.left is not None:
            node_list.extend(self.show_preorder(node.left))
        if node.right is not None:
            node_list.extend(self.show_preorder(node.right))

        return node_list

    def show_inorder(self, node):
        node_list = []

        if node.left is not None:
            node_list.extend(self.show_inorder(node.left))
        node_list.append(node.key)
        if node.right is not None:
            node_list.extend(self.show_inorder(node.right))

        return node_list

    def print(self):
        print(' ' + ' '.join(map(str, self.show_inorder(self.root))))
        print(' ' + ' '.join(map(str, self.show_preorder(self.root))))


if __name__ == '__main__':
    tree = BinarySearchTree()

    n = int(input())

    for i in range(n):
        command = input().split()

        if command[0] == 'insert':
            tree.insert(int(command[1]))
        elif command[0] == 'find':
            tree.find(int(command[1]))
        elif command[0] == 'print':
            tree.print()

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


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

    def insert(self, key):
        root_node = self.root
        insert_node = Node(key)
        parent_node = None

        while root_node:
            parent_node = root_node
            if insert_node.key < root_node.key:
                root_node = root_node.left
            else:
                root_node = root_node.right

        insert_node.parent = parent_node

        if parent_node is None:
            self.root = insert_node
        elif insert_node.key < parent_node.key:
            parent_node.left = insert_node
        else:
            parent_node.right = insert_node

    def find(self, key):
        root_node = self.root

        while root_node:
            if root_node.key == key:
                print('yes')
                return 0
            elif root_node.key < key:
                root_node = root_node.right
            else:
                root_node = root_node.left

        print('no')

    def show_preorder(self, node):
        node_list = []

        node_list.append(node.key)
        if node.left is not None:
            node_list.extend(self.show_preorder(node.left))
        if node.right is not None:
            node_list.extend(self.show_preorder(node.right))

        return node_list

    def show_inorder(self, node):
        node_list = []

        if node.left is not None:
            node_list.extend(self.show_inorder(node.left))
        node_list.append(node.key)
        if node.right is not None:
            node_list.extend(self.show_inorder(node.right))

        return node_list

    def print(self):
        print(' ' + ' '.join(map(str, self.show_inorder(self.root))))
        print(' ' + ' '.join(map(str, self.show_preorder(self.root))))


if __name__ == '__main__':
    tree = BinarySearchTree()

    n = int(input())

    for i in range(n):
        command = input().split()

        if command[0] == 'insert':
            tree.insert(int(command[1]))
        elif command[0] == 'find':
            tree.find(int(command[1]))
        elif command[0] == 'print':
            tree.print()

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

    def insert(self, insert_node):
        p = None
        r = self.root
        while r:
            p = r
            if insert_node.value < r.value:
                r = r.left
            else:
                r = r.right

        if not p:
            self.root = insert_node
        elif insert_node.value < p.value:
            p.left = insert_node
        else:
            p.right = insert_node

    def find(self, find_value):
        p = None
        r = self.root
        while r:
            p = r
            if find_value == r.value:
                return "yes"
            if find_value < r.value:
                r = r.left
            else:
                r = r.right
        return "no"

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

    def pre_order_search(self):
        l = self.left
        r = self.right
        print("",self.value, end="")
        if l:
            l.pre_order_search()
        if r:
            r.pre_order_search()

    def in_order_search(self):
        l = self.left
        r = self.right
        if l:
            l.in_order_search()
        print("",self.value, end="")
        if r:
            r.in_order_search()

m = int(input())
tree = BinaryTree()

for i in range(m):
    inp = input().split()
    if inp[0] == "insert":
        tree.insert(Node(int(inp[1]), None, None))
    elif inp[0] == "find":
        print(tree.find(int(inp[1])))
    else:
        tree.root.in_order_search()
        print()
        tree.root.pre_order_search()
        print()

Solution (Python):

import sys


class Node(object):
    __slots__ = ["value", "left", "right"]

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


class BinTree(object):
    def __init__(self):
        self._tree = None

    def insert(self, value):
        parent = None
        current = self._tree

        while current is not None:
            parent = current
            if value < current.value:
                current = current.left
            else:
                current = current.right

        if parent is None:
            self._tree = Node(value)
        elif value < parent.value:
            parent.left = Node(value)
        else:
            parent.right = Node(value)

    def find(self, value):
        current = self._tree

        while current is not None:
            if value == current.value:
                return True
            elif value < current.value:
                current = current.left
            else:
                current = current.right

        return False

    def preoder_walk(self):
        def preoder(node):
            result = []
            if node is None:
                pass
            else:
                result.append(node.value)
                result.extend(preoder(node.left))
                result.extend(preoder(node.right))
            return result

        return preoder(self._tree)

    def inorder_walk(self):
        def inorder(node):
            result = []
            if node is None:
                pass
            else:
                result.extend(inorder(node.left))
                result.append(node.value)
                result.extend(inorder(node.right))
            return result

        return inorder(self._tree)


def print_tree(tree):
    print(" " + " ".join([str(val) for val in tree.inorder_walk()]))
    print(" " + " ".join([str(val) for val in tree.preoder_walk()]))


def print_yes_no(boolean):
    if boolean:
        print("yes")
    else:
        print("no")


def main(commands):
    tree = BinTree()
    for com in commands:
        if com[0] == "insert":
            tree.insert(int(com[1]))
        elif com[0] == "print":
            print_tree(tree)
        elif com[0] == "find":
            print_yes_no(tree.find(int(com[1])))
        else:
            raise ValueError


if __name__ == "__main__":
    n = int(input())
    commands = [com.split() for com in sys.stdin.readlines()]
    main(commands)

Solution (Python):


class Node(object):

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

        self.key = key


class Tree(object):

    def __init__(self):
        self.root = None

    def insert(self, new_key):
        x = self.root
        y = None

        while x is not None:
            y = x

            if new_key < y.key:
                x = y.left
            else:
                x = y.right

        new_node = Node(new_key)
        new_node.parent = y
        if y is None:
            self.root = new_node
        elif new_key < y.key:
            y.left = new_node
        else:
            y.right = new_node

    def inorder(self, now):
        visited = list()
        if now is None:
            return visited

        visited.extend(self.inorder(now.left))
        visited.append(now.key)
        visited.extend(self.inorder(now.right))
        return visited

    def preorder(self, now):
        visited = list()
        if now is None:
            return visited

        visited.append(now.key)
        visited.extend(self.preorder(now.left))
        visited.extend(self.preorder(now.right))
        return visited

    def order_print(self):
        keys = list()
        keys.append(self.inorder(self.root))
        keys.append(self.preorder(self.root))

        for visited_keys in keys:
            print "",
            print " ".join(map(str, visited_keys))

    def find(self, key):
        """
        keys = self.inorder(self.root)
        if key in keys:
            print "yes"
        else:
            print "no"
        """
        x = self.root
        y = None

        while not (x is None or x.key == key):
            y = x
            if key < y.key:
                x = y.left
            else:
                x = y.right

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


    def min_node(self, now):
        """min_node
        Return the node with the minimum key,
        treeting now as the root of a sub tree.
        """
        if now.left is not None:
            return min_node(now.left)
        return now


    def delete(self, key):
        x = self.root
        y = None

        while x.key != key:
            y = x
            if key < y.key:
                x = y.left
            else:
                x = y.right

        
        if x.left is None and x.right is None:
            if y.left == x:
                y.left = None
            else:
                y.right = None
        elif x.left is None or x.right is None:
            child = x.left if x.left is not None else x.right
            child.parent = y
            if y.left == x:
                y.left = child
            else:
                y.right = child
        else:
            next_node = self.min_node(x.right)
            x.key = next_node.key
            self.delete(next_node)


def main():
    tree = Tree()

    num_orders = int(raw_input())
    for _ in xrange(num_orders):
        order = raw_input()
        if order[0] == 'i':
            new_key = int(order.split()[1])
            tree.insert(new_key)
        elif order[0] == 'p':
            tree.order_print()
        elif order[0] == 'f':
            key = int(order.split()[1])
            tree.find(key)
        elif order[0] == 'd':
            key = int(order.split()[1])
            tree.delete(key)


if __name__ == "__main__":
    main()

Solution (Python):



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


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

    def insert(self, z):
        z = Node(z)
        y = None
        x = self.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:
            self.root = z
        elif z.key < y.key:
            y.left = z
        else:
            y.right = z

    def preorder(self):
        def preParse(u):
            if u == None:
                return
            print(" " + str(u.key), end="")
            preParse(u.left)
            preParse(u.right)
        preParse(self.root)
        print("")

    def inorder(self):
        def inParse(u):
            if u == None:
                return
            inParse(u.left)
            print(" " + str(u.key), end="")
            inParse(u.right)
        inParse(self.root)
        print("")

    def print(self):
        self.inorder()
        self.preorder()

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

if __name__ == '__main__':

    n = int(input())
    command = [input().split(" ") for _ in range(n)]
    T = BinarySearchTree()

    for c in command:
        if c[0] == "insert":
            T.insert(int(c[1]))
        elif c[0] == "find":
            f = T.find(int(c[1]))
            if f is None:
                print("no")
            else:
                print("yes")
        else:
            T.print()

Solution (Python):
import sys
readline = sys.stdin.readline
class Node:
    __slots__ = ['value', 'left', 'right']
    def __init__(self, value = None, left = None, right = None):
        self.value = value
        self.left = left
        self.right = right
class BinTree:
    def __init__(self):
        self._tree = None
        self._node_list = set()
    def insert(self, value):
        self._node_list.add(value)
        p = None
        c = self._tree
        while c is not None:
            p = c
            if value < c.value:
                c = c.left
            else:
                c = c.right
        if p is None:
            self._tree = Node(value)
        elif value < p.value:
            p.left = Node(value)
        else:
            p.right = Node(value)
    def find(self, value):
        print("yes" if value in self._node_list else "no")
    def preoder_walk(self):
        def preoder(node):
            result = []
            if node is not None:
                result.extend([node.value])
            if node.left is not None:
                result.extend(preoder(node.left))
            if node.right is not None:
                result.extend(preoder(node.right))
            return result
        return preoder(self._tree)
    def inorder_walk(self):
        def inorder(node):
            result = []
            if node is not None:
                result.extend(inorder(node.left))
                result.append(node.value)
                result.extend(inorder(node.right))
            return result
        return inorder(self._tree)
n = int(input())
tree = BinTree()
for _ in range(n):
    com = readline().split()
    if com[0] == "insert":
        tree.insert(int(com[1]))
    elif com[0] == "find":
        tree.find(int(com[1]))
    else:
        print(" " + " ".join(map(str, tree.inorder_walk())))
        print(" " + " ".join(map(str, tree.preoder_walk())))

Solution (Python):
import sys
readline = sys.stdin.readline
class Node:
    __slots__ = ['value', 'left', 'right']
    def __init__(self, value = None, left = None, right = None):
        self.value = value
        self.left = left
        self.right = right
class BinTree:
    __slots__ = ['_tree', '_node_list']
    def __init__(self):
        self._tree = None
        self._node_list = set()
    def insert(self, value):
        self._node_list.add(value)
        p = None
        c = self._tree
        while c is not None:
            p = c
            if value < c.value:
                c = c.left
            else:
                c = c.right
        if p is None:
            self._tree = Node(value)
        elif value < p.value:
            p.left = Node(value)
        else:
            p.right = Node(value)
    def find(self, value):
        print("yes" if value in self._node_list else "no")
    def preoder_walk(self):
        def preoder(node):
            result = []
            if node is not None:
                result.extend([node.value])
            if node.left is not None:
                result.extend(preoder(node.left))
            if node.right is not None:
                result.extend(preoder(node.right))
            return result
        return preoder(self._tree)
    def inorder_walk(self):
        def inorder(node):
            result = []
            if node is not None:
                result.extend(inorder(node.left))
                result.append(node.value)
                result.extend(inorder(node.right))
            return result
        return inorder(self._tree)
n = int(input())
tree = BinTree()
for _ in range(n):
    com = readline().split()
    if com[0] == "insert":
        tree.insert(int(com[1]))
    elif com[0] == "find":
        tree.find(int(com[1]))
    else:
        print(" " + " ".join(map(str, tree.inorder_walk())))
        print(" " + " ".join(map(str, tree.preoder_walk())))

Solution (Python):
import sys
readline = sys.stdin.readline
class Node:
    __slots__ = ['value', 'left', 'right']
    def __init__(self, value = None, left = None, right = None):
        self.value = value
        self.left = left
        self.right = right
class BinTree:
    def __init__(self):
        self._tree = None
    def insert(self, value):
        p = None
        c = self._tree
        while c is not None:
            p = c
            if value < c.value:
                c = c.left
            else:
                c = c.right
        if p is None:
            self._tree = Node(value)
        elif value < p.value:
            p.left = Node(value)
        else:
            p.right = Node(value)
    def find(self, value):
        c = self._tree
        while c is not None:
            if value == c.value:
                return True
            elif value < c.value:
                c = c.left
            else:
                c = c.right
        return False
    def preoder_walk(self):
        self.result = []
        def preoder(node):
            if node is not None:
                self.result.append(node.value)
                preoder(node.left)
                preoder(node.right)
        preoder(self._tree)
        print(" " + " ".join(map(str, self.result)))
    def inorder_walk(self):
        self.result = []
        def inorder(node):
            if node is not None:
                inorder(node.left)
                self.result.append(node.value)
                inorder(node.right)
        inorder(self._tree)
        print(" " + " ".join(map(str, self.result)))
n = int(input())
tree = BinTree()
for _ in range(n):
    com = readline().split()
    if com[0] == "insert":
        tree.insert(int(com[1]))
    elif com[0] == "find":
        print("yes" if tree.find(int(com[1])) else "no")
    else:
        tree.inorder_walk()
        tree.preoder_walk()

Solution (Python):
import sys
readline = sys.stdin.readline
class Node:
    __slots__ = ['value', 'left', 'right']
    def __init__(self, value = None, left = None, right = None):
        self.value = value
        self.left = left
        self.right = right
class BinTree:
    __slots__ = ['_tree', 'result']
    def __init__(self):
        self._tree = None
    def insert(self, value):
        p = None
        c = self._tree
        while c is not None:
            p = c
            if value < c.value:
                c = c.left
            else:
                c = c.right
        if p is None:
            self._tree = Node(value)
        elif value < p.value:
            p.left = Node(value)
        else:
            p.right = Node(value)
    def find(self, value):
        c = self._tree
        while c is not None:
            if value == c.value:
                return True
            elif value < c.value:
                c = c.left
            else:
                c = c.right
        return False
    def preoder_walk(self):
        self.result = []
        def preoder(node):
            if node is not None:
                self.result.append(node.value)
                preoder(node.left)
                preoder(node.right)
        preoder(self._tree)
        print(" " + " ".join(map(str, self.result)))
    def inorder_walk(self):
        self.result = []
        def inorder(node):
            if node is not None:
                inorder(node.left)
                self.result.append(node.value)
                inorder(node.right)
        inorder(self._tree)
        print(" " + " ".join(map(str, self.result)))
n = int(input())
tree = BinTree()
for _ in range(n):
    com = readline().split()
    if com[0] == "insert":
        tree.insert(int(com[1]))
    elif com[0] == "find":
        print("yes" if tree.find(int(com[1])) else "no")
    else:
        tree.inorder_walk()
        tree.preoder_walk()

Solution (Python):
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 != None: x, y = x.left if key < x.key else x.right, x
    if y == 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 == None

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] == 'f': print(['yes','no'][find(int(e[5:]))])
    else: print(inorder(root)); print(preorder(root))

Solution (Python):
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 != None: x, y = x.left if key < x.key else x.right, x
    if y == 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 == None

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] == 'f': print(['yes','no'][find(int(e[5:]))])
    else: print(inorder(root)); print(preorder(root))

Solution (Python):
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 != None: x, y = x.left if key < x.key else x.right, x
    if y == 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 == None

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] == 'f': print(['yes','no'][find(int(e[5:]))])
    else: print(inorder(root)); print(preorder(root))

Solution (Python):
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 != None: x, y = x.left if key < x.key else x.right, x
    if y == 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 == None

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] == 'f': print(['yes','no'][find(int(e[5:]))])
    else: print(inorder(root)); print(preorder(root))

Solution (Python):
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 != None: x, y = x.left if key < x.key else x.right, x
    if y == 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 == None

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] == 'f': print(['yes','no'][find(int(e[5:]))])
    else: print(inorder(root)); print(preorder(root))