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: Wrong Answer

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

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

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

def find(k):
    global root
    x = root
    while x is not None:
        if x.key is k:
            print "yes"
            return
        elif x.key > k:
            x = x.left
        else:
            x = x.right
    print "no"

def pre_order(node, list):
    if node is not None:
        list.append(node.key)
        pre_order(node.left, list)
        pre_order(node.right, list)

def in_order(node, list):
    if node is not None:
        in_order(node.left, list)
        list.append(node.key)
        in_order(node.right, list)

m = int(raw_input())
root = None
for i in range(m):
    line = map(str, raw_input().split())
    if line[0] == "insert":
        z = Node_Class(int(line[1]), None, None, None)
        insert(z)
    elif line[0] == "find":
        find(int(line[1]))
    else:
        A = []
        B = []
        in_order(root, A)
        pre_order(root, B)
        print " "+" ".join(map(str, A))
        print " "+" ".join(map(str, B))

Submission status: Wrong Answer

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

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

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

def find(k):
    global root
    x = root
    while x != None:
        if x.key == k:
            print "yes"
            return
        elif k < x.key:
            x = x.left
        else:
            x = x.right
    print "no"

def pre_order(node):
    global s2
    if node is not None:
        s2 = s2 + " " + str(node.key)
        pre_order(node.left)
        pre_order(node.right)

def in_order(node):
    global s1
    if node is not None:
        in_order(node.left)
        s1 = s1 + " " + str(node.key)
        in_order(node.right)

m = int(raw_input())
root = None
s1 = ''
s2 = ''
for i in range(m):
    line = map(str, raw_input().split())
    if line[0] == "insert":
        z = Node_Class(int(line[1]), None, None, None)
        insert(z)
    elif line[0] == "find":
        find(int(line[1]))
    else:
        print s1
        print s2

Submission status: Wrong Answer

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

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

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

def find(k):
    global root
    x = root
    while x != None:
        if x.key == k:
            print "yes"
            return
        elif k < x.key:
            x = x.left
        else:
            x = x.right
    print "no"

def pre_order(node):
    global s2
    if node is not None:
        s2 = s2 + " " + str(node.key)
        pre_order(node.left)
        pre_order(node.right)

def in_order(node):
    global s1
    if node is not None:
        in_order(node.left)
        s1 = s1 + " " + str(node.key)
        in_order(node.right)

m = int(raw_input())
root = None
s1 = ''
s2 = ''
for i in range(m):
    line = map(str, raw_input().split())
    if line[0] == "insert":
        z = Node_Class(int(line[1]), None, None, None)
        insert(z)
    elif line[0] == "find":
        find(int(line[1]))
    else:
        in_order(root)
        pre_order(root)
        print s1
        print s2

Submission status: Wrong Answer

Solution code:
import sys
import time

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

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

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

def inorderTreeWalk(node):
    global In
    if node:
        inorderTreeWalk(node.left)
        In.append(str(node.key))
        inorderTreeWalk(node.right)

def preorderTreeWalk(node):
    global Pre
    if node:
        Pre.append(str(node.key))
        preorderTreeWalk(node.left)
        preorderTreeWalk(node.right)

if __name__ == "__main__":
    lines = sys.stdin.readlines()
    del lines[0]

    root = None
    for line in lines:
        if line[0] == "p":
            In = []
            Pre = []
            inorderTreeWalk(root)
            print " " + " ".join(map(str, In))
            preorderTreeWalk(root)
            print " " + " ".join(map(str, Pre))
        else:
            com = line.split()
            if com[0][0] == "i":
                insert(Node(int(com[1])))
            else:
                if find(root, int(com[1])):
                    print "yes"
                else:
                    print "no"

Submission status: Wrong Answer

Solution code:
class BinarySearchTree:
    def __init__(self):
        self.root = None
    def insert(self, z):
        p = None
        x = self.root
        while x != None:
            p = x
            if z.key < x.key : x = x.left
            else             : x = x.right
        z.p = p
        if p == None      : self.root = z
        elif z.key < p.key: p.left  = z
        else              : p.right = z
    def get_inorder_list(self):
        def _get_inorder_list(root):
            l = root.left
            r = root.right
            if l: yield from _get_inorder_list(l)
            yield root.key
            if r: yield from _get_inorder_list(r)
        yield from _get_inorder_list(self.root)
    def get_preorder_list(self):
        def _get_preorder_list(root):
            l = root.left
            r = root.right
            yield root.key
            if l: yield from _get_preorder_list(l)
            if r: yield from _get_preorder_list(r)
        yield from _get_preorder_list(self.root)
    def find(self, k):
        def _find(k, x):
            if x == None : return False
            if x.key == k: return True
            return _find(k, x.left) or _find(k, x.right)
        return _find(k, self.root)

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

if __name__=='__main__':
    m = int(input())

    T = BinarySearchTree()
    for _ in range(m):        
        op = input().split()
        if   op[0] == 'insert': T.insert( Node(int(op[1])) )
        elif op[0] == 'find':
            print("Yes" if T.find(int(op[1])) else "No")
        else:
            print("",*T.get_inorder_list())
            print("",*T.get_preorder_list())

Submission status: Wrong Answer

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

def inorder(n):
    if n != None:
        inorder(n.left)
        print n.v,
        inorder(n.right)

def preorder(n):
    if n != None:
        print n.v,
        preorder(n.left)
        preorder(n.right)

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

    def insert(self,v):
        n = Node(v)
        x = self.root
        y = None
        while x != None:
            y = x
            if x.v > v:
                x = x.left
            else:
                x = x.right
        if y == None:
            self.root = n
        else:
            if y.v > v:
                y.left = n
            else:
                y.right = n
    def print_tree(self):
        print '',
        inorder(self.root)
        print
        print '',
        preorder(self.root)
        print


n = int(raw_input())
ops = []
for _ in range(n):
    ops.append(raw_input())

tree = BST()
for op in ops:
    if op[0] == 'i':
        num = op.split(' ')[1]
        num = int(num)
        tree.insert(num)
    else:
        tree.print_tree()

Submission status: Wrong Answer

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 != 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.left
    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))

Submission status: Wrong Answer

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

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":
        tree.find(tree.root, int(com[1]))
    else:
        tree.print()

Submission status: Wrong Answer

Solution code:
#coding:utf-8
N = int(input())
trees = [list(input().split()) for i in range(N)]

class BinaryTree:
    def __init__(self,key,p=None,l=None,r=None):
        self.key = key
        self.p = p
        self.l = l
        self.r = r

def Insert(root,z):
    y = None
    x = root
    while x != None:
        y = x
        if z.key < x.key:
            x = x.l
        else:
            x = x.r
    z.p = y

    if y == None:
        root = z
    elif z.key < y.key:
        y.l = z
    else:
        y.r = z
    return root

def preOrder(root):
    x = root
    if x == None:
        return
    global preList
    preList.append(x.key)
    
    preOrder(x.l)
    preOrder(x.r)

def inOrder(root):
    x = root
    if x == None:
        return
    inOrder(x.l)

    global inList
    inList.append(x.key)
    
    inOrder(x.r)

def Find(root,target):
    x = root
    if x == None:
        return   
    if x.key == target:
        print("yes")
        return
    Find(x.l,target)
    Find(x.r,target)
    print("no")

root = None
for data in trees:
    if data[0] == "insert":
        z = BinaryTree(int(data[1]))
        root = Insert(root,z)
    if data[0] == "find":
        Find(root, data[1])
        
    if data[0] == "print":
        inList = []
        preList = []
        inOrder(root)
        a = " ".join([str(num) for num in inList])
        print(a)

        preOrder(root)
        a = " ".join([str(num) for num in preList])
        print(a)

Submission status: Time Limit Exceeded

Solution code:
from __future__ import print_function
from sys import stdin
class Node:
    def __init__(self, id):
        self.id = id
        self.left = None
        self.right = None
        self.parent = None

def preorder_tree_walk(root):
    print('', root.id, end='')
    if root.left != None:
        preorder_tree_walk(root.left)
    if root.right != None:
        preorder_tree_walk(root.right)

def inorder_tree_walk(root):
    if root.left != None:
        inorder_tree_walk(root.left)
    print('', root.id, end='')
    if root.right != None:
        inorder_tree_walk(root.right)

def insert(root, z):
    y = None
    x = root
    while isinstance(x, Node):
        y = x
        if z.id < x.id:
            x = x.left
        else:
            x = x.right
    z.parent = y

    if y == None:
        root = z
    elif z.id < y.id:
        y.left = z
    else:
        y.right = z
    return root

def find(root, x):
    if root.id == x:
        return True

    if root.id > x:
        if root.left == None:
            return False
        else:
            return find(root.left, x)
    else:
        if root.right == None:
            return False
        else:
            return find(root.right, x)

n = int(raw_input())
root = None
for i in xrange(n):
    cmd = stdin.readline()
    if cmd.startswith('i'):
        num = int(cmd[7:])
        root = insert(root, Node(num))
    elif cmd.startswith('p'):
        inorder_tree_walk(root)
        print()
        preorder_tree_walk(root)
        print()
    else:
        # find
        num = int(cmd[5:])
        if find(root, num):
            print('yes')
        else:
            print('no')

Submission status: Time Limit Exceeded

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

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

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

def find(k):
    global root
    x = root
    while x != None:
        if x.key == k:
            print "yes"
            return
        elif k < x.key:
            x = x.left
        else:
            x = x.right
    print "no"

def pre_order(node, list):
    if node is not None:
        list.append(node.key)
        pre_order(node.left, list)
        pre_order(node.right, list)

def in_order(node, list):
    if node is not None:
        in_order(node.left, list)
        list.append(node.key)
        in_order(node.right, list)

m = int(raw_input())
root = None
for i in range(m):
    line = map(str, raw_input().split())
    if line[0] == "insert":
        z = Node_Class(int(line[1]), None, None, None)
        insert(z)
    elif line[0] == "find":
        find(int(line[1]))
    else:
        A = []
        B = []
        in_order(root, A)
        pre_order(root, B)
        print " "+" ".join(map(str, A))
        print " "+" ".join(map(str, B))

Submission status: Time Limit Exceeded

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

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

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

def find(k):
    global root
    x = root
    while x != None:
        if x.key == k:
            print "yes"
            return
        elif k < x.key:
            x = x.left
        else:
            x = x.right
    print "no"

def pre_order(node):
    if node is not None:
        pl.append(node.key)
        pre_order(node.left)
        pre_order(node.right)

def in_order(node):
    if node is not None:
        in_order(node.left)
        il.append(node.key)
        in_order(node.right)
m = int(raw_input())
root = None
for i in range(m):
    line = map(str, raw_input().split())
    if line[0] == "insert":
        z = Node_Class(int(line[1]), None, None, None)
        insert(z)
    elif line[0] == "find":
        find(int(line[1]))
    else:
        pl = []
        il = []
        pre_order(root)
        in_order(root)
        print " "+" ".join(map(str, il))
        print " "+" ".join(map(str, pl))

Submission status: Time Limit Exceeded

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

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

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

def find(k):
    x = root
    while x != None:
        if x.key == k:
            print "yes"
            return
        elif k < x.key:
            x = x.left
        else:
            x = x.right
    print "no"

def pre_order(node):
    if node is not None:
        pl.append(node.key)
        pre_order(node.left)
        pre_order(node.right)

def in_order(node):
    if node is not None:
        in_order(node.left)
        il.append(node.key)
        in_order(node.right)

m = int(raw_input())
root = None
for i in range(m):
    line = map(str, raw_input().split())
    if line[0][0] == 'i':
        z = Node_Class(int(line[1]), None, None, None)
        insert(z)
    elif line[0][0] == 'f':
        find(int(line[1]))
    else:
        pl = []
        il = []
        pre_order(root)
        in_order(root)
        print " "+" ".join(map(str, il))
        print " "+" ".join(map(str, pl))

Submission status: Time Limit Exceeded

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

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

def insert(k):
    global root
    y = None
    x = root
    z = Node_Class(k, None, None, None)
    while x != None:
        y = x
        if z.key < x.key:
            x = x.left
        else:
            x = x.right
    z.parent = y
    if y is None:
        root = z
    elif z.key < y.key:
        y.left = z
    else:
        y.right = z

def find(k):
    global root
    x = root
    while x != None:
        if x.key == k:
            print "yes"
            return
        elif k < x.key:
            x = x.left
        else:
            x = x.right
    print "no"

def pre_order(node):
    if node is not None:
        pl.append(node.key)
        pre_order(node.left)
        pre_order(node.right)

def in_order(node):
    if node is not None:
        in_order(node.left)
        il.append(node.key)
        in_order(node.right)

m = int(raw_input())
root = None
for i in range(m):
    line = map(str, raw_input().split())
    if line[0] == "insert":
        insert(int(line[1]))
    elif line[0] == "find":
        find(int(line[1]))
    else:
        pl = []
        il = []
        pre_order(root)
        in_order(root)
        print " "+" ".join(map(str, il))
        print " "+" ".join(map(str, pl))

Submission status: Time Limit Exceeded

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

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

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

def find(k):
    global root
    x = root
    while x != None:
        if x.key == k:
            print "yes"
            return
        elif k < x.key:
            x = x.left
        else:
            x = x.right
    print "no"

def pre_order(node):
    global s2
    if node is not None:
        s2 = s2 + " " + str(node.key)
        pre_order(node.left)
        pre_order(node.right)

def in_order(node):
    global s1
    if node is not None:
        in_order(node.left)
        s1 = s1 + " " + str(node.key)
        in_order(node.right)

m = int(raw_input())
root = None
for i in range(m):
    line = map(str, raw_input().split())
    if line[0] == "insert":
        z = Node_Class(int(line[1]), None, None, None)
        insert(z)
    elif line[0] == "find":
        find(int(line[1]))
    else:
        s1 = ""
        s2 = ""
        in_order(root)
        pre_order(root)
        print s1
        print s2

Submission status: Time Limit Exceeded

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

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

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

def find(k):
    global root
    x = root
    while x != None:
        if x.key == k:
            print "yes"
            return
        elif k < x.key:
            x = x.left
        else:
            x = x.right
    print "no"

def pre_order(node):
    if node is not None:
        print node.key,
        pre_order(node.left)
        pre_order(node.right)

def in_order(node):
    if node is not None:
        in_order(node.left)
        print node.key,
        in_order(node.right)

m = int(raw_input())
root = None
for i in range(m):
    line = map(str, raw_input().split())
    if line[0] == "insert":
        z = Node_Class(int(line[1]), None, None, None)
        insert(z)
    elif line[0] == "find":
        find(int(line[1]))
    else:
        print "",
        in_order(root)
        print
        print "",
        pre_order(root)
        print

Submission status: Time Limit Exceeded

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

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

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

def find(k):
    global root
    x = root
    while x != None:
        if x.key == k:
            print "yes"
            return
        elif k < x.key:
            x = x.left
        else:
            x = x.right
    print "no"

def pre_order(node):
    if node is not None:
        print node.key,
        pre_order(node.left)
        pre_order(node.right)

def in_order(node):
    if node is not None:
        in_order(node.left)
        print node.key,
        in_order(node.right)

m = int(raw_input())
root = None
for i in range(m):
    line = map(str, raw_input().split())
    if line[0] == "insert":
        z = Node_Class(int(line[1]))
        insert(z)
    elif line[0] == "find":
        find(int(line[1]))
    else:
        print "",
        in_order(root)
        print
        print "",
        pre_order(root)
        print

Submission status: Time Limit Exceeded

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

import sys

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

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

def find(k):
    global root
    x = root
    while x != None:
        if x.key == k:
            print "yes"
            return
        elif k < x.key:
            x = x.left
        else:
            x = x.right
    print "no"

def pre_order(node):
    if node != None:
        print node.key,
        pre_order(node.left)
        pre_order(node.right)

def in_order(node):
    if node != None:
        in_order(node.left)
        print node.key,
        in_order(node.right)

m = int(raw_input())
root = None
for i in range(m):
    line = sys.stdin.readline()
    if line[0] == "i":
        z = Node_Class(int(line[7:]))
        insert(z)
    elif line[0] == "f":
        find(int(line[5:]))
    else:
        print "",
        in_order(root)
        print
        print "",
        pre_order(root)
        print

Submission status: Time Limit Exceeded

Solution code:
import sys
import time

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

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

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

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

def inorderTreeWalk(node):
    if node:
        return inorderTreeWalk(node.left) + " " + str(node.key) + inorderTreeWalk(node.right)
    return ""

def preorderTreeWalk(node):
    if node:
        return " " + str(node.key) + preorderTreeWalk(node.left) + preorderTreeWalk(node.right)
    return ""

if __name__ == "__main__":
    lines = sys.stdin.readlines()
    del lines[0]

    root = None
    for line in lines:
        if line[0] == "p":
            print inorderTreeWalk(root)
            print preorderTreeWalk(root)
        else:
            com = line.split()
            if com[0][0] == "i":
                insert(int(com[1]))
            else:
                if find(root, int(com[1])):
                    print "yes"
                else:
                    print "no"

Submission status: Time Limit Exceeded

Solution code:
import sys
import time

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

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

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

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

def inorderTreeWalk(node):
    if node:
        return inorderTreeWalk(node.left) + " " + str(node.key) + inorderTreeWalk(node.right)
    return ""

def preorderTreeWalk(node):
    if node:
        return " " + str(node.key) + preorderTreeWalk(node.left) + preorderTreeWalk(node.right)
    return ""

if __name__ == "__main__":
    lines = sys.stdin.readlines()
    del lines[0]

    root = None
    for line in lines:
        if line[0] == "p":
            print inorderTreeWalk(root)
            print preorderTreeWalk(root)
        else:
            com = line.split()
            if com[0][0] == "i":
                insert(int(com[1]))
            else:
                if find(root, int(com[1])):
                    print "yes"
                else:
                    print "no"