Problem:

  MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }});

Binary Search Tree I

 Search trees are data structures that support dynamic set operations including insert, search, delete and so on. Thus a search tree can be used both as a dictionary and as a priority queue. 

  Binary search tree is one of fundamental search trees. The keys in a binary search tree are always stored in such a way as to satisfy the following binary search tree property:

 Let $x$ be a node in a binary search tree. If $y$ is a node in the left subtree of $x$, then $y.key \leq x.key$. If $y$ is a node in the right subtree of $x$, then $x.key \leq y.key$.

  The following figure shows an example of the binary search tree.

  For example, keys of nodes which belong to the left sub-tree of the node containing 80 are less than or equal to 80, and keys of nodes which belong to the right sub-tree are more than or equal to 80. The binary search tree property allows us to print out all the keys in the tree in sorted order by an inorder tree walk.

  A binary search tree should be implemented in such a way that the binary search tree property continues to hold after modifications by insertions and deletions. A binary search tree can be represented by a linked data structure in which each node is an object. In addition to a key field and satellite data, each node contains fields left, right, and p that point to the nodes corresponding to its left child, its right child, and its parent, respectively.

  To insert a new value $v$ into a binary search tree $T$, we can use the procedure insert as shown in the following pseudo code. The insert procedure is passed a node $z$ for which $z.key = v$, $z.left = NIL$, and $z.right = NIL$. The procedure modifies $T$ and some of the fields of $z$ in such a way that $z$ is inserted into an appropriate position in the tree.

1 insert(T, z)
2     y = NIL // parent of x
3     x = 'the root of T'
4     while x &ne; NIL
5         y = x // set the parent
6         if z.key < x.key
7             x = x.left // move to the left child
8         else 
9             x = x.right // move to the right child
10    z.p = y
11
12    if y == NIL // T is empty
13        'the root of T' = z
14    else if z.key < y.key
15        y.left = z // z is the left child of y
16    else 
17        y.right = z // z is the right child of y

  Write a program which performs the following operations to a binary search tree $T$.

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

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

  You should use the above pseudo code to implement the insert operation. $T$ is empty at the initial state.

Input

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

Output

  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

8
insert 30
insert 88
insert 12
insert 1
insert 20
insert 17
insert 25
print

Sample Output 1

 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:
8
insert 30
insert 88
insert 12
insert 1
insert 20
insert 17
insert 25
print


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

Submission status: Wrong Answer

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

def insert(node, x):
    if node is None:
        return Node(x)
    elif x == node.key:
        return node
    elif x < node.key:
        node.left = insert(node.left, x)
    else:
        node.right = insert(node.right, x)
    return node

def preorder(node):
    if node == None:
        return None
    l.append(node.key)
    preorder(node.left)
    preorder(node.right)
    return l

def inorder(node):
    if node == None:
        return None
    inorder(node.left)
    l.append(node.key)
    inorder(node.right)
    return l

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

    def insert(self, x):
        self.root = insert(self.root, x)

l = []
tree = BinaryTree()
n = int(input())

for i in range(n):
    order = list(map(str, input().split()))
    if order[0] == "insert":
        tree.insert(order[1])
    if order[0] == "print":
        inorder(tree.root)
        for i in range(len(l)):
            if i != len(l)-1:
                print(l[i],end=" ")
            else:
                print(l[i])
        l.clear()

        preorder(tree.root)
        for i in range(len(l)):
            if i != len(l)-1:
                print(l[i],end=" ")
            else:
                print(l[i])
        exit()
    else:
        continue

Submission status: Wrong Answer

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

def insert(node, x):
    if node is None:
        return Node(x)
    elif x == node.key:
        return node
    elif x < node.key:
        node.left = insert(node.left, x)
    else:
        node.right = insert(node.right, x)
    return node

def preorder(node):
    if node == None:
        return None
    l.append(node.key)
    preorder(node.left)
    preorder(node.right)
    return l

def inorder(node):
    if node == None:
        return None
    inorder(node.left)
    l.append(node.key)
    inorder(node.right)
    return l

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

    def insert(self, x):
        self.root = insert(self.root, x)

    def output(self):
        print(self.root.key)
        print(self.root.left.key)
        print(self.root.right.key)

l = []
tree = BinaryTree()
n = int(input())

for i in range(n):
    order = list(map(str, input().split()))
    if order[0] == "insert":
        tree.insert(int(order[1]))
    if order[0] == "print":
        tree.output()
        inorder(tree.root)
        for i in range(len(l)):
            if i != len(l)-1:
                print(l[i],end=" ")
            else:
                print(l[i])
        l.clear()

        preorder(tree.root)
        for i in range(len(l)):
            if i != len(l)-1:
                print(l[i],end=" ")
            else:
                print(l[i])
        exit()
    else:
        continue

Submission status: Wrong Answer

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

def insert(node, x):
    if node is None:
        return Node(x)
    elif x == node.key:
        return node
    elif x < node.key:
        node.left = insert(node.left, x)
    else:
        node.right = insert(node.right, x)
    return node

def preorder(node):
    if node == None:
        return None
    l.append(node.key)
    preorder(node.left)
    preorder(node.right)
    return l

def inorder(node):
    if node == None:
        return None
    inorder(node.left)
    l.append(node.key)
    inorder(node.right)
    return l

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

    def insert(self, x):
        self.root = insert(self.root, x)

    def output(self):
        print(self.root.key)
        print(self.root.left.key)
        print(self.root.right.key)

l = []
tree = BinaryTree()
n = int(input())

for i in range(n):
    order = list(map(str, input().split()))
    if order[0] == "insert":
        tree.insert(int(order[1]))
    if order[0] == "print":
        inorder(tree.root)
        for i in range(len(l)):
            if i != len(l)-1:
                print(" ",end="")
                print(l[i],end="")
            else:
                print(" ",end="")
                print(l[i])
        l.clear()

        preorder(tree.root)
        for i in range(len(l)):
            if i != len(l)-1:
                print(" ",end="")
                print(l[i],end="")
            else:
                print(" ",end="")
                print(l[i])
        exit()
    else:
        continue

Submission status: Wrong Answer

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

@author: maezawa
"""

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

class tree():
    def __init__(self, top):
        self.root = top
        
def insert(t, z):
    y = None
    x = t.root
    while x != None:
        y = x
        if z.key < x.key:
            x = x.left
        else:
            x = x.right
    z.parent = y
    
    if y == None:
        t.root = z
    elif z.key < y.key:
        y.left = z
    else:
        y.right = z
        
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)
    
t = tree(None) 

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

Submission status: Wrong Answer

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

class tree():
    def __init__(self, top):
        self.root = top
        
def insert(t, z):
    y = None
    x = t.root
    while x != None:
        y = x
        if z.key < x.key:
            x = x.left
        else:
            x = x.right
    z.parent = y
    
    if y == None:
        t.root = z
    elif z.key < y.key:
        y.left = z
    else:
        y.right = z  
    
        
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)
    
t = tree(None) 

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

Submission status: Wrong Answer

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 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
    preParse(u.l)
    preParse(u.r)
    global preParseList
    preParseList.append(u.key)


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]))
    else:
        inParse(root)
        preParse(root)

        print(" ".join([str(i) for i in inParseList]))
        print(" ".join([str(i) for i in preParseList]))

Submission status: Wrong Answer

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 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]))
    else:
        inParse(root)
        preParse(root)

        print(" " + " ".join([str(i) for i in inParseList]))
        print(" " + " ".join([str(i) for i in preParseList]))

Submission status: Wrong Answer

Solution code:
class BinaryTree:

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


    def __init__(self):
        self.root = None

    def insert(self, key):
        if self.root is None:
            self.root = self.Node(key)
        else:
            root = self.root
            temp = None
            while True:
                temp = root
                if key > root.key:
                    root = root.right
                    if root is None:
                        temp.right = self.Node(key)
                        break
                else:
                    root = root.left
                    if root is None:
                        temp.left = self.Node(key)
                        break
        return self

    def print_inorder(self, node):
        if node is not None:
            self.print_inorder(node.left)
            print(node.key, end = " ")
            self.print_inorder(node.right)

    def print_preorder(self, node):
        if node is not None:
            print(node.key, end = " ")
            self.print_inorder(node.left)
            self.print_inorder(node.right)

length = int(input())
b = BinaryTree()
for _ in range(length):
    comm = input()
    if comm[0] == "i":
        com, num = comm.split(" ")
        b.insert(int(num))
    else:
        b.print_inorder(b.root)
        b.print_preorder(b.root)

Submission status: Wrong Answer

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

class BST:
  root = None
  def insert(self, k):
    x = self.root
    y = None
    z = Node(k)
    while x is not None:
      y = x
      if z.key < y.key:
        x = x.left
      elif y.key < z.key:
        x = x.right
    
    if y is None:
      # 初回値
      self.root = z
    else:
      if z.key < y.key:
        y.left = z
      elif y.key < z.key:
        y.right = z
        
  def inorder(self):
    # 先行巡回順で出力
    res = []
    cur_node = self.root
    right_successor = []
    left_successor = []
    # 現在の木がなにもない場合
    if cur_node is None:
      return res
    # そうでない場合
    while cur_node is not None:
      res.append(cur_node.key)
      # 次に調べるやつを追加する
      if cur_node.left is not None:
        left_successor.append(cur_node.left)
      if cur_node.right is not None:
        right_successor.append(cur_node.right)
      # 次に調べるやつを左、右の順でやっていく
      cur_node = left_successor.pop() if len(left_successor) > 0 else right_successor.pop() if len(right_successor) else None
    return res
      
n = int(input())
bst = BST()
for _ in range(n):
  query = [int(x) if x.isnumeric() else x for x in input().split()]
  if query[0] == 'insert':
    bst.insert(query[1])
  elif query[0] == 'print':
    ans = bst.inorder()
    print(" " + " ".join(list(map(str, ans))))

Submission status: Wrong Answer

Solution code:
import re

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

class BST:
  root = None
  def insert(self, k):
    x = self.root
    y = None
    z = Node(k)
    while x is not None:
      y = x
      if z.key < y.key:
        x = x.left
      elif y.key < z.key:
        x = x.right
    
    if y is None:
      # 初回値
      self.root = z
    else:
      if z.key < y.key:
        y.left = z
      elif y.key < z.key:
        y.right = z
        
  def inorder(self, r):
    # 中間巡回順で出力
    if r != None:
      self.preorder(r.left)
      print(" {}".format(r.key), end="")
      self.preorder(r.right)
      

  def preorder(self, r):
    # 先行巡回順で出力
    if r != None:
      print(" {}".format(r.key), end="")
      self.preorder(r.left)
      self.preorder(r.right)

    
n = int(input())
bst = BST()
for _ in range(n):
  query = [int(x) if re.match('[+|-]?\d', x) else x for x in input().split()]
  if query[0] == 'insert':
    bst.insert(query[1])
  elif query[0] == 'print':
    root = bst.root
    bst.inorder(root)
    print()
    bst.preorder(root)
    print()

Submission status: Wrong Answer

Solution code:
import re

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

class BST:
  root = None
  def insert(self, k):
    x = self.root
    y = None
    z = Node(k)
    while x is not None:
      y = x
      if z.key < y.key:
        x = x.left
      elif y.key < z.key:
        x = x.right
    
    if y is None:
      # 初回値
      self.root = z
    else:
      if z.key < y.key:
        y.left = z
      elif y.key < z.key:
        y.right = z
        
  def inorder(self, r):
    # 中間巡回順で出力
    if r != None:
      self.inorder(r.left)
      print(" {}".format(r.key), end="")
      self.inorder(r.right)
      

  def preorder(self, r, lis):
    # 先行巡回順で出力
    if r != None:
      lis.append(r.key)
      self.preorder(r.left, lis)
      self.preorder(r.right, lis)

    
n = int(input())
bst = BST()
for _ in range(n):
  # query = [int(x) if re.match('[+|-]?\d', x) else x for x in input().split()]
  query = input().split()
  if query[0] == 'insert':
    bst.insert(int(query[1]))
  elif query[0] == 'print':
    root = bst.root
    lis = []
    bst.preorder(root, lis)
    print(" "+ " ".join(list(map(str, lis))))
    print(" "+ " ".join(sorted(list(map(str, lis)))))
    print()

Submission status: Wrong Answer

Solution code:
import re

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

class BST:
  root = None
  def insert(self, k):
    x = self.root
    y = None
    z = Node(k)
    while x is not None:
      y = x
      if z.key < y.key:
        x = x.left
      elif y.key < z.key:
        x = x.right
    
    if y is None:
      # 初回値
      self.root = z
    else:
      if z.key < y.key:
        y.left = z
      elif y.key < z.key:
        y.right = z
  """      
  def inorder(self, r):
    # 中間巡回順で出力
    if r != None:
      self.inorder(r.left)
      print(" {}".format(r.key), end="")
      self.inorder(r.right)
  """    

  def preorder(self, r, lis):
    # 先行巡回順で出力
    if r != None:
      lis.append(r.key)
      self.preorder(r.left, lis)
      self.preorder(r.right, lis)

    
n = int(input())
bst = BST()
for _ in range(n):
  # query = [int(x) if re.match('[+|-]?\d', x) else x for x in input().split()]
  query = input().split()
  if query[0] == 'insert':
    bst.insert(int(query[1]))
  elif query[0] == 'print':
    root = bst.root
    lis = []
    bst.preorder(root, lis)
    print(" " + " ".join(sorted(list(map(str, lis)))))
    print(" " + " ".join(list(map(str, lis))))

Submission status: Wrong Answer

Solution code:
import copy

def selection_sort(A,n):
    for i in range(n):
        minj = i
        for j in range(i,n):
            if A[j] < A[minj]:
                minj = j
        A[i],A[minj] = A[minj], A[i]
    return A

n = int(input())
r = [0]*n
for i in range(n):
    r[i] = input().split()

for i in range(n):
    if r[i][0] == "insert":
        root= int(r[i][1])
        key = i + 1
        break
    else:
        print()
        print()

left = []
right = []
for i in range(key, n):
    if r[i][0] == "insert" and int(r[i][1]) < root:
        left += [int(r[i][1])]
    elif r[i][0] == "insert" and int(r[i][1]) > root:
        right += [int(r[i][1])]
    else:
        pre = [root]+ left + right
        a = copy.deepcopy(pre)
        print([], *selection_sort(a,len(a)))
        print([], *pre)

Submission status: Wrong Answer

Solution code:
import copy

def selection_sort(A,n):
    for i in range(n):
        minj = i
        for j in range(i,n):
            if A[j] < A[minj]:
                minj = j
        A[i],A[minj] = A[minj], A[i]
    return A

n = int(input())
r = [0]*n
for i in range(n):
    r[i] = input().split()

for i in range(n):
    if r[i][0] == "insert":
        root= int(r[i][1])
        key = i + 1
        break
    else:
        print()
        print()

left = []
right = []
for i in range(key, n):
    if r[i][0] == "insert" and int(r[i][1]) < root:
        left += [int(r[i][1])]
    elif r[i][0] == "insert" and int(r[i][1]) > root:
        right += [int(r[i][1])]
    else:
        pre = [root]+ left + right
        a = copy.deepcopy(pre)
        print(pre)
        print("　", *selection_sort(a,len(a)))
        print("　", *pre)

Submission status: Wrong Answer

Solution code:
class Node:
    def __init__(self, key):
        self.key = key
        self.parent = None
        self.left = None
        self.right = None
class Tree:
    def __init__(self):
        self.root = None
        self.inorder = []
        self.preorder = []

    def insert(self, node):

        p = None
        x = self.root        
        while x is not None:
            p = x
            # print(node.key, x.key)
            if node.key <= x.key:
                x = x.left
            else:
                x = x.right

        # insertするnodeの親を設定
        node.parent = p

        if p is None:
            self.root = node
        else:
            # insertするnodeを親のleftかrightに設定
            if node.key <= p.key:
                # print('leftに設定')
                p.left = node
            else:
                # print('rightに設定')
                p.right = node


    def print_inorder(self):
        self.inorder_traverse(self.root)
        print(' ' + ' '.join(map(str, self.inorder)))

    def print_preorder(self):
        self.preorder_traverse(self.root)
        print(' ' + ' '.join(map(str, self.preorder)))

    def inorder_traverse(self, node):
        if node is None:
            return
        self.inorder_traverse(node.left)
        self.inorder.append(node.key)
        self.inorder_traverse(node.right)

    def preorder_traverse(self, node):
        if node is None:
            return
        self.preorder.append(node.key)
        self.preorder_traverse(node.left)
        self.preorder_traverse(node.right)

tree = Tree()
m = int(input())
for i in range(m):
    line = input().split()
    if line[0] == 'print':
        tree.print_inorder()
        tree.print_preorder()
    elif line[0] == 'insert':
        key = int(line[1])
        tree.insert(Node(key))
    elif line[0] == 'find':
        key = int(line[1])
        if tree.find(key):
            print('yes')
        else:
            print('no')
    elif line[0] == 'delete':
        print("current tree----")
        print(tree.root.key)
        print(tree.root.left.key)
        print(tree.root.left.right.key)
        print("current tree----")
        key = int(line[1])
        node = tree.find(key)
        tree.delete(node)

Submission status: Wrong Answer

Solution code:
class Node:
    def __init__(self, key):
        self.key = key
        self.parent = None
        self.left = None
        self.right = None
class Tree:
    def __init__(self):
        self.root = None
        self.inorder = []
        self.preorder = []

    def insert(self, node):

        p = None
        x = self.root        
        while x is not None:
            p = x
            # print(node.key, x.key)
            if node.key <= x.key:
                x = x.left
            else:
                x = x.right

        # insertするnodeの親を設定
        node.parent = p

        if p is None:
            self.root = node
        else:
            # insertするnodeを親のleftかrightに設定
            if node.key <= p.key:
                # print('leftに設定')
                p.left = node
            else:
                # print('rightに設定')
                p.right = node


    def print_inorder(self):
        self.inorder_traverse(self.root)
        print(' ' + ' '.join(map(str, self.inorder)))

    def print_preorder(self):
        self.preorder_traverse(self.root)
        print(' ' + ' '.join(map(str, self.preorder)))

    def inorder_traverse(self, node):
        if node is None:
            return
        self.inorder_traverse(node.left)
        self.inorder.append(node.key)
        self.inorder_traverse(node.right)

    def preorder_traverse(self, node):
        if node is None:
            return
        self.preorder.append(node.key)
        self.preorder_traverse(node.left)
        self.preorder_traverse(node.right)

tree = Tree()
m = int(input())
for i in range(m):
    line = input().split()
    if line[0] == 'print':
        tree.print_inorder()
        tree.print_preorder()
    elif line[0] == 'insert':
        key = int(line[1])
        tree.insert(Node(key))
    # elif line[0] == 'find':
    #     key = int(line[1])
    #     if tree.find(key):
    #         print('yes')
    #     else:
    #         print('no')
    # elif line[0] == 'delete':
    #     print("current tree----")
    #     print(tree.root.key)
    #     print(tree.root.left.key)
    #     print(tree.root.left.right.key)
    #     print("current tree----")
    #     key = int(line[1])
    #     node = tree.find(key)
    #     tree.delete(node)

Submission status: Wrong Answer

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

def insert(tree,k):
    y = None
    x = tree
    z = Node(k)
    while x != None:
        y = x
        if x.key > k:
            x = x.left
        else:
            x = x.right
    z.p = y
    if y == None:
        tree = z
    elif y.key > k:
        y.left = z
    else:
        y.right = z
    return tree

def middleorder(x):
    if x != None:
        middleorder(x.left)
        print x.key,
        middleorder(x.right)

def preorder(x):
    if x != None:
        print x.key,
        preorder(x.left)
        preorder(x.right)



tree = None
m = int(raw_input())
for i in range(m):
    c = raw_input().strip()
    if c[0] == 'i':
        tree = insert(tree, c[7:])
    elif c[0] == 'p':
        print '',
        middleorder(tree)
        print
        print '',
        preorder(tree)
        print

Submission status: Wrong Answer

Solution code:

class Node:
    def __init__(self, key=-1):
        self.key = key
        self.parent = -1
        self.left = -1
        self.right = -1
    
    def setKey(self, key):
        self.key = key


def insert(T_, z): #(T, Node)
    global T
    y = -1
    x = T_ #Node()
    while x != -1 :
        y = x
        if z.key < x.key:
            x = x.left
        else:
            x = x.right
    z.parent = y
    if y == -1:
        T = z
    elif z.key < y.key:
        y.left = z
    else:
        y.right = z


def preParse(T):
    if T == -1 :
        return
    print T.key,
    preParse(T.left)
    preParse(T.right)

def inParse(T):
    if T == -1 :
        return
    inParse(T.left) #Node() or -1
    print T.key,
    inParse(T.right)


T = -1

def main():
    com = []
    m = int(raw_input())
    #for i in xrange(m):
    #    com.append(raw_input())
    for i in xrange(m):
        com.append(raw_input())
        if com[0] == 'i':
            insert(T,Node(key=int(com[7:])))
        else:
            print '',
            inParse(T)
            print
            print '',
            preParse(T)
            print 
    return 0

main()

Submission status: Wrong Answer

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

def insert(T,z):
    x=T
    y=None
    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:
        T=z
    elif z.key<y.key:
        y.left=z
    else:
        y.right=z
    return T
        
def preorder(u):
    if not isinstance(u,node):
        return
    pripre.append(str(u.key))
    preorder(u.left)
    preorder(u.right)

def inorder(u):
    if not isinstance(u,node):
        return
    inorder(u.left)
    priin.append(str(u.key))
    inorder(u.right)

pripre=[]
priin=[]
m=input()
root=None
for i in xrange(m):
    cmd=map(str,raw_input().split())
    if cmd[0]=="print":
        preorder(root)
        inorder(root)
        print(' '+' '.join(priin))
        print(' '+' '.join(pripre))
    else:
        key=int(cmd[1])
        z=node(key)
        root=insert(root,z)

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 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)
    else:
        A = []
        B = []
        pre_order(root, A)
        in_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 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 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
pl = []
il = []
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)
    else:
        print " "+" ".join(map(str, il))
        print " "+" ".join(map(str, pl))