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: Time Limit Exceeded

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: Time Limit Exceeded

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 find(self,v):
        x = self.root
        while x != None:
            if x.v == v:
                return True
            elif x.v < v:
                x = x.right
            else:
                x = x.left
        return False

    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)
    elif op[0] == 'f':
        num = op.split(' ')[1]
        num = int(num)
        if tree.find(num):
            print 'yes'
        else:
            print 'no'
    else:
        tree.print_tree()

Submission status: Time Limit Exceeded

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

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

  # usage
  # btree.insert(btree.root, n)
  def insert(self, node, n):
    if node.label == None:
      node.label = n
    elif n < node.label:
      if node.left == None:
        node.left = Node(n)
      else:
        node.left = self.insert(node.left, n)
    else:
      if node.right == None:
        node.right = Node(n)
      else:
        node.right = self.insert(node.right, n)
    return node

  # usage
  # btree.printer(btree.root)
  def printer(self, node):
    labels = []
    if node.left != None:
      labels.extend(self.printer(node.left))
    labels.append(node.label)
    if node.right != None:
      labels.extend(self.printer(node.right))
    return labels

  # usage
  # btree.printer_c(btree.root)
  def printer_c(self, node):
    labels = []
    labels.append(node.label)
    if node.left != None:
      labels.extend(self.printer_c(node.left))
    if node.right != None:
      labels.extend(self.printer_c(node.right))
    return labels

  def find(self, node, x):
    if node == None:
      return False
    elif node.label == x:
      return True
    elif x < node.label:
      return self.find(node.left, x)
    elif node.label < x:
      return self.find(node.right, x)

btree = BinaryTree()
n = int(raw_input())
for _ in xrange(n):
  op = raw_input().split()
  if op[0] == "insert":
    btree.insert(btree.root, int(op[1]))
  elif op[0] == "print":
    print " "+" ".join(map(str, btree.printer(btree.root)))
    print " "+" ".join(map(str, btree.printer_c(btree.root)))
  elif op[0] == "find":
    judge = btree.find(btree.root, int(op[1]))
    if judge:
      print "yes"
    else:
      print "no"

Submission status: Time Limit Exceeded

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 print1(node):
        if node.left != None:
            Node.print1(node.left)
        print("",node.data,  end="")
        if node.right != None:
            Node.print1(node.right)
    def print2(node):
        print("",node.data,  end="")
        if node.left != None:
            Node.print2(node.left)
        if node.right != None:
            Node.print2(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 print_tree(self):
        Node.print1(self.root)
        print()
        Node.print2(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]))
        else:
            z = int(s.split()[1])
            T.insert(z)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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: Time Limit Exceeded

Solution code:
class Node():
    def __init__(self, id, left=-1, right=-1, parent=-1, type=None):
        self.id = id
        self.left = left
        self.right = right
        self.parent = parent
        
    def show(self):
        print 'node %d: parent = %d, left = %d, right = %d' % (self.id, self.parent, self.left, self.right)

class Stack():
    def __init__(self):
        self.el = []
    def add(self, el):
        self.el.append(el)
    def pop(self):
        return self.el.pop()
        
def hasChild(x):
    if x == -1:
        return 0
    return 1

def printOrder(T):
    global rootId
    ### inorder ###
    pos = rootId
    st = Stack()
    ans = []
    while True:
        if T[pos].left != -1 and T[pos].left not in ans:
            if T[pos].right != -1:
                st.add(T[pos].right)
            st.add(pos)
            pos = T[pos].left
        elif T[pos].left == -1 and T[pos].right != -1 and T[pos].right not in ans:
            ans.append(pos)
            pos = T[pos].right
        else:
            ans.append(pos)
            if len(ans) == len(T):
                break
            pos = st.pop()
    print '', ' '.join(map(str, ans))
    ### preorder ###
    pos = rootId
    st = Stack()
    ans = []
    while True:
        ans.append(pos)
        if len(ans) == len(T):
            break
        if T[pos].left != -1 and T[pos].right != -1:
            st.add(T[pos].right)
        if T[pos].left != -1:
            pos = T[pos].left
        elif T[pos].left == -1 and T[pos].right != -1:
            pos = T[pos].right
        else:
            pos = st.pop()
    print '', ' '.join(map(str, ans))

def insert(T, z):
    global rootId
    y = None
    if rootId:
        x = T[rootId]
        while x != None:
            y = x
            if z.id < x.id:
                if x.left == -1:
                    break
                x = T[x.left]
            else:
                if x.right == -1:
                    break
                x = T[x.right]
        z.parent = x.id
    if y == None:
        rootId = z.id
    elif z.id < y.id:
        y.left = z.id
    else:
        y.right = z.id
    T[z.id] = z
    return T

def find(T, z):
    global rootId
    y = None
    if rootId:
        x = T[rootId]
        while True:
            y = x
            if z == x.id:
                print 'yes'
                break
            elif z < x.id:
                if x.left == -1:
                    print 'no'
                    break
                x = T[x.left]
            else:
                if x.right == -1:
                    print 'no'
                    break
                x = T[x.right]
                
### input ###
T = {}
a = []
n = int(raw_input())
rootId = None
for i in range(n):
    tmp = raw_input().split()
    if tmp[0] == 'insert':
        T[int(tmp[1])] = Node(int(tmp[1]))
        T = insert(T, Node(int(tmp[1])))
    elif tmp[0] == 'find':
        find(T, int(tmp[1]))
    elif tmp[0] == 'print':
        printOrder(T)

Submission status: Time Limit Exceeded

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

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

    def insert(self,x):
        if self.root == None:
            self.root = Node(x)
        cur = self.root
        while True:
            if cur.value > x:
                if cur.left == None:
                    cur.left = Node(x)
                    break
                cur = cur.left
            elif cur.value < x:
                if cur.right == None:
                    cur.right = Node(x)
                    break
                cur = cur.right
            else:
                break

    def find(self,x):
        cur = self.root
        if cur == None:
            return False
        while True:
            if cur.value > x:
                if cur.left != None:
                    cur = cur.left
                else:
                    return False
            elif cur.value < x:
                if cur.right != None:
                    cur = cur.right
                else:
                    return False
            else:
                return True

    def mprint(self):
        print '',
        print ' '.join(map(str, self.inorder(self.root)))
        print '',
        print ' '.join(map(str, self.preorder(self.root)))

    def inorder(self, cur):
        ret = []
        if cur.left != None:
            ret += self.inorder(cur.left)
        ret.append(cur.value)
        if cur.right != None:
            ret += self.inorder(cur.right)
        return ret

    def preorder(self, cur):
        ret = []
        ret.append(cur.value)
        if cur.left != None:
            ret += self.preorder(cur.left)
        if cur.right != None:
            ret += self.preorder(cur.right)
        return ret



m = int(raw_input())
tree = BST()
commands = []
for _ in range(m):
    line = raw_input()
    if line[0] == 'i':
        num = int(line.split(' ')[1])
        commands.append(('insert', num))
    elif line[0] == 'p':
        commands.append(('print', '-1'))
    elif line[0] == 'f':
        num = int(line.split(' ')[1])
        commands.append(('find', num))
    else:
        raise Exception("Unknown command")

for cmd, num in commands:
    if cmd == 'insert':
        tree.insert(num)
    elif cmd == 'print':
        tree.mprint()
    elif cmd == 'find':
        if tree.find(num):
            print 'yes'
        else:
            print 'no'

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from enum import Enum, auto

class Color(Enum):
    WHITE = auto()
    GRAY = auto()
    BLACK = auto()

class BinaryTreeNode():
    def __init__(self, parent=None, left=None, right=None, val=None):
        self.parent = parent
        self.left = left
        self.right = right
        self.val = val
        self.color = Color.WHITE

class BinarySearchTree():
    def __init__(self):
        self.root = None
        self.nodes = deque([])

    def set_root(self, val):
        node = BinaryTreeNode(val=val)
        self.root = len(self.nodes)
        self.nodes.append(node)

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

        if y == None:
            self.set_root(val)
        elif node.val < self.nodes[y].val:
            self.nodes[y].left = len(self.nodes)
            self.nodes.append(node)
        else:
            self.nodes[y].right = len(self.nodes)
            self.nodes.append(node)

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

    def init_color(self):
        for node in self.nodes:
            node.color = Color.WHITE

    def preorder(self):
        preordered = []
        self.init_color()
        def preorder_bfs(s):
            preordered.append(self.nodes[s].val)
            self.nodes[s].color = Color.GRAY
            if  self.nodes[s].left != None and self.nodes[self.nodes[s].left].color == Color.WHITE:
                preorder_bfs(self.nodes[s].left)
            if  self.nodes[s].right != None and self.nodes[self.nodes[s].right].color == Color.WHITE:
                preorder_bfs(self.nodes[s].right)
                self.nodes[s].color = Color.BLACK
        preorder_bfs(self.root)
        return preordered

    def inorder(self):
        inordered = []
        self.init_color()

        inorder_stack = deque([])
        def inorder_dfs_init(s):
            inorder_stack.append(s)
            inorder_dfs()

        def inorder_dfs():
            u = inorder_stack.pop()
            self.nodes[u].color = Color.GRAY
            if self.nodes[u].left != None and self.nodes[self.nodes[u].left].color == Color.WHITE:
                inorder_stack.append(u)
                inorder_stack.append(self.nodes[u].left)
                inorder_dfs()
            inordered.append(self.nodes[u].val)
            if self.nodes[u].right != None and self.nodes[self.nodes[u].right].color == Color.WHITE:
                inorder_stack.append(self.nodes[u].right)
                inorder_dfs()
            self.nodes[u].color = Color.BLACK

        inorder_dfs_init(self.root)
        return inordered

def print_elements(ordered):
    for ele in ordered:
        print(' {}'.format(ele), end='')
    print('')

m = int(input())
bst = BinarySearchTree()
for i in range(m):
    op = input()
    if op == 'print':
        print_elements(bst.inorder())
        print_elements(bst.preorder())
        continue
    ope, num = op.split(' ')
    num = int(num)
    if ope == 'insert':
        bst.insert(num)
    elif ope == 'find':
        if bst.find(num):
            print('yes')
        else:
            print('no')

Submission status: Time Limit Exceeded

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(x):
    if x == None:
        return
    global preList
    preList.append(x.key)
    
    preOrder(x.l)
    preOrder(x.r)

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

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

def Find(x,target):
    if x == None:
        return 
    if x.key == target:
        global yes
        yes = True
        return True
    Find(x.l,target)
    Find(x.r,target)

root = None
for data in trees:
    if data[0] == "insert":
        z = BinaryTree(int(data[1]))
        root = Insert(root,z)
    if data[0] == "find":
        yes = False
        a = Find(root, int(data[1]))
        if yes:
            print("yes")
        else:
            print("no")
        
    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:
#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin


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


def tree_insert(top, z):
    y = None
    x = top
    while isinstance(x, Node):
        y = x
        if z.key < x.key:
            x = x.left
        else:
            x = x.right
    z.parent = y
    if y is None:
        top = z
    elif z.key < y.key:
        y.left = z
    else:
        y.right = z
    return top


def tree_find(node, key):
    if not node:
        return False
    if node.key == key:
        return True
    return tree_find(node.left, key) or tree_find(node.right, key)


def inorder_walk(node):
    if node.left:
        inorder_walk(node.left)
    print('', node.key, end='')
    if node.right:
        inorder_walk(node.right)


def preorder_walk(node):
    print('', node.key, end='')
    if node.left:
        preorder_walk(node.left)
    if node.right:
        preorder_walk(node.right)


n = int(stdin.readline())
#assert n <= 500000

top = None
for _ in range(n):
    cmd = stdin.readline()
    if cmd.startswith('i'):
        key = int(cmd[7:])
        #assert -2000000000 <= key <= 2000000000
        top = tree_insert(top, Node(key))
    elif cmd.startswith('f'):
        key = int(cmd[5:])
        r = tree_find(top, key)
        print('yes' if r else 'no')
    else:
        inorder_walk(top)
        print()
        preorder_walk(top)
        print()

Submission status: Accepted

Solution code:
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 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 outorder(self):
        def outparse(u):
            if u == None:
                return
            print(" " + str(u.key), end="")
            outparse(u.left)
            outparse(u.right)
        outparse(self.root)
        print("")
 
    def print(self):
        self.inorder()
        self.outorder()
 
    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
 
n = int(input())
clist = [input().split(" ") for i in range(n)]
tree = binarysearchtree()

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

Submission status: Accepted

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


def Pre(t, l):
    l.append(str(t.n))
    if t.left != None:
        Pre(t.left, l)
    if t.right != None:
        Pre(t.right, l)


def In(t, l):
    if t.left != None:
        In(t.left, l)
    l.append(str(t.n))
    if t.right != None:
        In(t.right, l)


def insert(t, z):
    y = None
    x = t
    while x != None:
        y = x
        if z.n < x.n:
            x = x.left
        else:
            x = x.right
    if y == None:
        return z
    else:
        if z.n < y.n:
            y.left = z
        else:
            y.right = z
        return t


def Find(t, p):
    if t.n == p:
        return True
    elif t.left != None and t.n > p:
        a = Find(t.left, p)
    elif t.right != None and t.n < p:
        a = Find(t.right, p)
    else:
        return False
    return a


def BST2(A, n):
    tree = None
    for i in range(n):
        if A[i] == "print":
            PreAns = []
            InAns = []
            Pre(tree, PreAns)
            In(tree, InAns)
            print(" "+" ".join(InAns))
            print(" "+" ".join(PreAns))
        else:
            if A[i].split(" ")[0] == "find":
                c = "no"
                point = int(A[i].split(" ")[1])
                if Find(tree, point) == True:
                    print("yes")
                else:
                    print("no")

            else:
                z = Node(int(A[i].split(" ")[1]))
                tree = insert(tree, z)


if __name__ == "__main__":
    n = int(input())
    A = []
    for i in range(n):
        A.append(input())
    BST2(A, n)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Thu Jul 19 22:51:44 2018

@author: maezawa
"""

class node():
    def __init__(self, key, parent=None, right=None, left=None):
        self.key = key
        self.parent = parent
        self.right = right
        self.left = left
        
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 == None:
        root = z
    elif z.key < y.key:
        y.left = z
    else:
        y.right = z  
    #inorder(root)
    
def find(x, k):
    while x != None and k != x.key:
        if k < x.key:
            x = x.left
        else:
            x = x.right
    return x
        
def inorder(u):
    if u == None:
        return
    inorder(u.left)
    print(' {}'.format(u.key), end = '')
    inorder(u.right)
    
def preorder(u):
    if u == None:
        return
    print(' {}'.format(u.key), end = '')
    preorder(u.left)
    preorder(u.right)
    
root = None

n = int(input())
for i in range(n):
    q = list(input().split())
    if q[0] == 'insert':
        z = node(int(q[1]))
        insert(z)
    elif q[0] == 'find':
        if find(root, int(q[1])):
            print('yes')
        else:
            print('no')
    elif q[0] == 'print':
        inorder(root)
        print()
        preorder(root)
        print()

Submission status: Accepted

Solution code:
#coding:utf-8

class MakeTree():
    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,value):
    y = None
    x = root
    z = MakeTree(value)

    while x != None:
        y = x
        if x.key > z.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 Find(u, target):
    y = None
    x = u
    while x != None and target != x.key:
        y = x
        if x.key > target:
            x = x.l
        else:
            x = x.r
    if x == None:
        print("no")
    else:
        print("yes")
            
    

def inParse(u):
    if u == None:
        return
    inParse(u.l)
    global inParseList
    inParseList.append(u.key)
    inParse(u.r)

def preParse(u):
    if u == None:
        return
    global preParseList
    preParseList.append(u.key)
    preParse(u.l)
    preParse(u.r)


root = None       
n = int(input())
inParseList = []
preParseList = []
for i in range(n):
    order = list(input().split())
    if order[0] == "insert":
        root = Insert(root, int(order[1]))
        
    elif order[0] == "print":
        inParse(root)
        preParse(root)
        print(" " + " ".join([str(i) for i in inParseList]))
        print(" " + " ".join([str(i) for i in preParseList]))
        preParseList = []
        inParseList = []
        
    elif order[0] == "find":
        Find(root, int(order[1]))