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

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

class BinaryTreeNode():
    __slots__ = ['left', 'right', 'val']
    def __init__(self, left=None, right=None, val=None):
        self.left = left
        self.right = right
        self.val = val

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

    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)

        if y == None:
            self.root = 0
        elif node.val < self.nodes[y].val:
            self.nodes[y].left = self.num_nodes
        else:
            self.nodes[y].right = self.num_nodes
        self.nodes.append(node)
        self.num_nodes += 1

    def preorder(self):
        def preorder_bfs(s):
            print('', self.nodes[s].val, end='')
            if  self.nodes[s].left != None:
                preorder_bfs(self.nodes[s].left)
            if  self.nodes[s].right != None:
                preorder_bfs(self.nodes[s].right)
        preorder_bfs(self.root)
        print('')

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

        def inorder_dfs():
            u = inorder_stack.pop()
            if self.nodes[u].left != None:
                inorder_stack.append(u)
                inorder_stack.append(self.nodes[u].left)
                inorder_dfs()
            print('', self.nodes[u].val, end='')
            if self.nodes[u].right != None:
                inorder_stack.append(self.nodes[u].right)
                inorder_dfs()

        inorder_dfs_init(self.root)
        print('')

m = int(input())
bst = BinarySearchTree()
for i in range(m):
    op = input()
    if op == 'print':
        bst.inorder()
        bst.preorder()
    else:
        num = int(op[7:])
        bst.insert(num)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

class BinaryTreeNode():
    __slots__ = ['left', 'right', 'val']
    def __init__(self, left=None, right=None, val=None):
        self.left = left
        self.right = right
        self.val = val

class BinarySearchTree():
    def __init__(self):
        self.root = None
        self.nodes = deque([])
        self.num_nodes = 0
        self.inorder_str = ''
        self.preorder_str = ''

    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)

        if y == None:
            self.root = 0
        elif node.val < self.nodes[y].val:
            self.nodes[y].left = self.num_nodes
        else:
            self.nodes[y].right = self.num_nodes
        self.nodes.append(node)
        self.num_nodes += 1

    def preorder(self):
        self.preorder_str = ''
        def preorder_bfs(s):
            self.preorder_str += ' ' + str(self.nodes[s].val)
            if  self.nodes[s].left != None:
                preorder_bfs(self.nodes[s].left)
            if  self.nodes[s].right != None:
                preorder_bfs(self.nodes[s].right)
        preorder_bfs(self.root)
        return self.preorder_str

    def inorder(self):
        self.inorder_str = ''
        inorder_stack = deque([])
        def inorder_dfs_init(s):
            inorder_stack.append(s)
            inorder_dfs()

        def inorder_dfs():
            u = inorder_stack.pop()
            if self.nodes[u].left != None:
                inorder_stack.append(u)
                inorder_stack.append(self.nodes[u].left)
                inorder_dfs()
            self.inorder_str += ' ' + str(self.nodes[u].val)
            if self.nodes[u].right != None:
                inorder_stack.append(self.nodes[u].right)
                inorder_dfs()

        inorder_dfs_init(self.root)
        return self.inorder_str

m = int(input())
bst = BinarySearchTree()
for i in range(m):
    op = input()
    if op == 'print':
        print(bst.inorder())
        print(bst.preorder())
    else:
        num = int(op[7:])
        bst.insert(num)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import time

class BinaryTreeNode():
    # __slots__ = ['left', 'right', 'val']
    def __init__(self, left=None, right=None, val=None):
        self.left = left
        self.right = right
        self.val = val

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

    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)

        if y == None:
            self.root = 0
        elif node.val < self.nodes[y].val:
            self.nodes[y].left = self.num_nodes
        else:
            self.nodes[y].right = self.num_nodes
        self.nodes.append(node)
        self.num_nodes += 1

    def preorder(self):
        self.preorder_list = []
        self.preorder_bfs(self.root)
        return self.preorder_list

    def preorder_bfs(self, u):
        if u == None: return
        self.preorder_list.append(self.nodes[u].val)
        self.preorder_bfs(self.nodes[u].left)
        self.preorder_bfs(self.nodes[u].right)

    def inorder(self):
        self.inorder_list = []
        self.inorder_dfs(self.root)
        return self.inorder_list

    def inorder_dfs(self, u):
        if u == None: return
        self.inorder_dfs(self.nodes[u].left)
        self.inorder_list.append(self.nodes[u].val)
        self.inorder_dfs(self.nodes[u].right)

def print_elements(arr):
    print(' ' + ' '.join([str(item) for item in arr]))

m = int(input())
bst = BinarySearchTree()
for i in range(m):
    op = input()
    if op == 'print':
        print_elements(bst.inorder())
        print_elements(bst.preorder())
    else:
        num = int(op[7:])
        bst.insert(num)

Submission status: Time Limit Exceeded

Solution code:
class NullNode():
    def __init__(self):
        self.id = -1

class Node():
    def __init__(self, id):
        self.id = id
        self.parent = NullNode()
        self.left = NullNode()
        self.right = NullNode()

    def __str__(self):
        return '{} {} {} {} {}'.format(self.id, self.parent.id, self.left.id, self.right.id, self.sibling.id)

def preorder(node, out_list=[]):
    if node.id != -1:
        out_list.append(str(node.id))
        out_list = preorder(node.left, out_list)
        out_list = preorder(node.right, out_list)
    return out_list

def inorder(node, out_list=[]):
    if node.id != -1:
        out_list = inorder(node.left, out_list)
        out_list.append(str(node.id))
        out_list = inorder(node.right, out_list)
    return out_list

def insert(node, root_node):
    temp_node_parent = root_node.parent
    temp_node = root_node

    while temp_node.id != -1:
        temp_node_parent = temp_node
        if node.id < temp_node.id:
            temp_node = temp_node.left
        else:
            temp_node = temp_node.right

    node.parent = temp_node_parent
    if node.id < temp_node_parent.id:
        temp_node_parent.left = node
    else:
        temp_node_parent.right = node




n = int(input())
node_list = []
for i in range(n):
    input_line = [i for i in input().split()]
    if input_line[0] == 'insert':
        id = int(input_line[1])
        id_node = Node(id)
        node_list.append(id_node)
        if i == 0:
            root_node = id_node
        else:
            insert(id_node, root_node)
    else:
        if i != 0:
            inorder_list = inorder(root_node, [])
            preorder_list = preorder(root_node, [])
            print(' ' + ' '.join(inorder_list))
            print(' ' + ' '.join(preorder_list))
        else:
            print()

Submission status: Time Limit Exceeded

Solution code:
class NullNode():
    def __init__(self):
        self.id = -1

class Node():
    def __init__(self, id):
        self.id = id
        self.parent = NullNode()
        self.left = NullNode()
        self.right = NullNode()

    def __str__(self):
        return '{} {} {} {} {}'.format(self.id, self.parent.id, self.left.id, self.right.id, self.sibling.id)

def preorder(node, out_list=[]):
    if node.id != -1:
        out_list.append(str(node.id))
        out_list = preorder(node.left, out_list)
        out_list = preorder(node.right, out_list)
    return out_list

def inorder(node, out_list=[]):
    if node.id != -1:
        out_list = inorder(node.left, out_list)
        out_list.append(str(node.id))
        out_list = inorder(node.right, out_list)
    return out_list

def insert(node, root_node):
    temp_node_parent = root_node.parent
    temp_node = root_node

    while temp_node.id != -1:
        temp_node_parent = temp_node
        if node.id < temp_node.id:
            temp_node = temp_node.left
        else:
            temp_node = temp_node.right

    node.parent = temp_node_parent
    if node.id < temp_node_parent.id:
        temp_node_parent.left = node
    else:
        temp_node_parent.right = node




n = int(input())

for i in range(n):
    input_line = [i for i in input().split()]
    if input_line[0] == 'insert':
        id = int(input_line[1])
        id_node = Node(id)
        if i == 0:
            root_node = id_node
        else:
            insert(id_node, root_node)
    else:
        inorder_list = inorder(root_node, [])
        preorder_list = preorder(root_node, [])
        print(' ' + ' '.join(inorder_list))
        print(' ' + ' '.join(preorder_list))

Submission status: Time Limit Exceeded

Solution code:
class NullNode():
    def __init__(self):
        self.id = None

class Node():
    def __init__(self, id):
        self.id = id
        self.parent = NullNode()
        self.left = NullNode()
        self.right = NullNode()

def preorder(node, out_list=[]):
    if node.id is not None:
        out_list.append(str(node.id))
        out_list = preorder(node.left, out_list)
        out_list = preorder(node.right, out_list)
    return out_list

def inorder(node, out_list=[]):
    if node.id is not None:
        out_list = inorder(node.left, out_list)
        out_list.append(str(node.id))
        out_list = inorder(node.right, out_list)
    return out_list

def insert(node, root_node):
    temp_node_parent = root_node.parent
    temp_node = root_node

    while temp_node.id is not None:
        temp_node_parent = temp_node
        if node.id < temp_node.id:
            temp_node = temp_node.left
        else:
            temp_node = temp_node.right

    node.parent = temp_node_parent
    if node.id < temp_node_parent.id:
        temp_node_parent.left = node
    else:
        temp_node_parent.right = node

def find(id,root_node):
    node = root_node
    while node.id is not None:
        if id < node.id:
            node = node.left
        elif id > node.id:
            node = node.right
        else:
            print('yes')
            break
    else:
        print('no')

def delete(id, root_node):
    # 作成中
    type = ''
    node = root_node
    node_parent = NullNode()
    while node.id != id:
        node_parent = node
        if id < node.id:
            node = node.left
            type = 'L'
        else:
            node = node.right
            type = 'R'
    if node.right is not None:
        node.right.parent = node_parent
    elif node.left is not None:
        node.left.parent = node_parent
    else:
        node.parent = NullNode()

    if type == 'L':
        node_parent.left = NullNode()
    else:
        node_parent.right = NullNode()


n = int(input())
root_node = NullNode()
for i in range(n):
    input_line = [i for i in input().split()]
    command = input_line[0]
    if command == 'insert':
        id = int(input_line[1])
        id_node = Node(id)
        if root_node.id is None:
            root_node = id_node
        else:
            insert(id_node, root_node)

    elif command == 'find':
        id = int(input_line[1])
        find(id, root_node)

    elif command == 'delete':
        id = int(input_line[1])
        delete(id, root_node)
    else:
        inorder_list = inorder(root_node, [])
        preorder_list = preorder(root_node, [])
        print(' ' + ' '.join(inorder_list))
        print(' ' + ' '.join(preorder_list))

Submission status: Time Limit Exceeded

Solution code:
class NullNode():
    def __init__(self):
        self.id = None

class Node():
    def __init__(self, id):
        self.id = id
        self.parent = NullNode()
        self.left = NullNode()
        self.right = NullNode()

def preorder(node, out_list=[]):
    if node.id is not None:
        out_list.append(str(node.id))
        out_list = preorder(node.left, out_list)
        out_list = preorder(node.right, out_list)
    return out_list

def inorder(node, out_list=[]):
    if node.id is not None:
        out_list = inorder(node.left, out_list)
        out_list.append(str(node.id))
        out_list = inorder(node.right, out_list)
    return out_list

def insert(node, root_node):
    temp_node_parent = root_node.parent
    temp_node = root_node

    while temp_node.id is not None:
        temp_node_parent = temp_node
        if node.id < temp_node.id:
            temp_node = temp_node.left
        else:
            temp_node = temp_node.right

    node.parent = temp_node_parent
    if node.id < temp_node_parent.id:
        temp_node_parent.left = node
    else:
        temp_node_parent.right = node

def find(id,root_node):
    node = root_node
    while node.id is not None:
        if id < node.id:
            node = node.left
        elif id > node.id:
            node = node.right
        else:
            print('yes')
            break
    else:
        print('no')

def delete(id, root_node):
    # 作成中
    type = ''
    node = root_node
    node_parent = NullNode()
    while node.id != id:
        node_parent = node
        if id < node.id:
            node = node.left
            type = 'L'
        else:
            node = node.right
            type = 'R'
    if node.right is not None:
        node.right.parent = node_parent
    elif node.left is not None:
        node.left.parent = node_parent
    else:
        node.parent = NullNode()

    if type == 'L':
        node_parent.left = NullNode()
    else:
        node_parent.right = NullNode()

import sys

n = int(input())
input_lines = sys.stdin.readlines()
root_node = NullNode()
for i in range(n):
    input_line = input_lines[i].split()
    command = input_line[0]
    if command == 'insert':
        id = int(input_line[1])
        id_node = Node(id)
        if root_node.id is None:
            root_node = id_node
        else:
            insert(id_node, root_node)

    elif command == 'find':
        id = int(input_line[1])
        find(id, root_node)

    elif command == 'delete':
        id = int(input_line[1])
        delete(id, root_node)
    else:
        inorder_list = inorder(root_node, [])
        preorder_list = preorder(root_node, [])
        print(' ' + ' '.join(inorder_list))
        print(' ' + ' '.join(preorder_list))

Submission status: Time Limit Exceeded

Solution code:
class NullNode():
    def __init__(self):
        self.id = None

class Node():
    def __init__(self, id):
        self.id = id
        self.parent = NullNode()
        self.left = NullNode()
        self.right = NullNode()

def preorder(node, out_list=[]):
    if node.id is not None:
        out_list.append(str(node.id))
        out_list = preorder(node.left, out_list)
        out_list = preorder(node.right, out_list)
    return out_list

def inorder(node, out_list=[]):
    if node.id is not None:
        out_list = inorder(node.left, out_list)
        out_list.append(str(node.id))
        out_list = inorder(node.right, out_list)
    return out_list

def insert(node, root_node):
    temp_node_parent = root_node.parent
    temp_node = root_node

    while temp_node.id is not None:
        temp_node_parent = temp_node
        if node.id < temp_node.id:
            temp_node = temp_node.left
        else:
            temp_node = temp_node.right

    node.parent = temp_node_parent
    if node.id < temp_node_parent.id:
        temp_node_parent.left = node
    else:
        temp_node_parent.right = node

# def find(id,root_node):
#     node = root_node
#     while node.id is not None:
#         if id < node.id:
#             node = node.left
#         elif id > node.id:
#             node = node.right
#         else:
#             print('yes')
#             break
#     else:
#         print('no')
#
# def delete(id, root_node):
#     # 作成中
#     type = ''
#     node = root_node
#     node_parent = NullNode()
#     while node.id != id:
#         node_parent = node
#         if id < node.id:
#             node = node.left
#             type = 'L'
#         else:
#             node = node.right
#             type = 'R'
#     if node.right is not None:
#         node.right.parent = node_parent
#     elif node.left is not None:
#         node.left.parent = node_parent
#     else:
#         node.parent = NullNode()
#
#     if type == 'L':
#         node_parent.left = NullNode()
#     else:
#         node_parent.right = NullNode()

import sys
n = int(input())
input_lines = sys.stdin.readlines()
root_node = NullNode()
for i in range(n):
    input_line = input_lines[i].split()
    command = input_line[0]
    if command == 'insert':
        id = int(input_line[1])
        id_node = Node(id)
        if root_node.id is None:
            root_node = id_node
        else:
            insert(id_node, root_node)

    # elif command == 'find':
    #     id = int(input_line[1])
    #     find(id, root_node)
    #
    # elif command == 'delete':
    #     id = int(input_line[1])
    #     delete(id, root_node)
    else:
        inorder_list = inorder(root_node, [])
        preorder_list = preorder(root_node, [])
        print(' ' + ' '.join(inorder_list))
        print(' ' + ' '.join(preorder_list))

Submission status: Time Limit Exceeded

Solution code:
import sys

tree={}
VALUE = 0
LEFT = 1
RIGHT = 2
np = -1

home=0
tree[home]=[None, None, None]

def search(p, x):
    while p != None:
        tmp = tree[p][VALUE]
        if tmp == x: return True
        if x < tmp:
            p = tree[p][LEFT]
        else:
            p = tree[p][RIGHT]
    return False

def node(x):
    global np
    np += 1
    tree[np] = [x, None, None]
    return np

def insert(p, x):
    if p == None or np == -1: return node(x)
    tmp = tree[p][VALUE]
    if x== tmp: return p
    elif x<tmp:
        tree[p][LEFT]=insert(tree[p][LEFT],x)
    else:
        tree[p][RIGHT]=insert(tree[p][RIGHT],x)
    return p

def preorder(p):
    if p == None: return []
    p1, p2 = tree[p][1:3]
    return [tree[p][VALUE]] + preorder(p1) + preorder(p2)

def inorder(p):
    if p == None: return []
    p1, p2 = tree[p][1:3]
    return inorder(p1) + [tree[p][VALUE]] +inorder(p2)

n = int(input())
i = 0
while i<n:
    s = raw_input()
    if s[0]=='i':
        insert(home,int(s[7:]))
    elif s[0]=='p':
        print ' ' + ' '.join(map(str, inorder(home)))
        print ' ' + ' '.join(map(str, preorder(home)))
    i += 1

Submission status: Time Limit Exceeded

Solution code:
import sys

tree={}
VALUE = 0
LEFT = 1
RIGHT = 2
np = -1

home=0
tree[home]=[None, None, None]

def search(p, x):
    while p != None:
        tmp = tree[p][VALUE]
        if tmp == x: return True
        if x < tmp:
            p = tree[p][LEFT]
        else:
            p = tree[p][RIGHT]
    return False

def insert(p, x):
    global np
    if p == None or np == -1:
        np += 1
        tree[np] = [x, None, None]
        return np
    tmp = tree[p][VALUE]
    if x== tmp: return p
    elif x<tmp:
        tree[p][LEFT]=insert(tree[p][LEFT],x)
    else:
        tree[p][RIGHT]=insert(tree[p][RIGHT],x)
    return p

def preorder(p):
    if p == None: return []
    p1, p2 = tree[p][1:3]
    return [tree[p][VALUE]] + preorder(p1) + preorder(p2)

def inorder(p):
    if p == None: return []
    p1, p2 = tree[p][1:3]
    return inorder(p1) + [tree[p][VALUE]] +inorder(p2)

n = int(input())
i = 0
while i<n:
    s = raw_input()
    if s[0]=='i':
        insert(home,int(s[7:]))
    elif s[0]=='p':
        print ' ' + ' '.join(map(str, inorder(home)))
        print ' ' + ' '.join(map(str, preorder(home)))
    i += 1

Submission status: Time Limit Exceeded

Solution code:
import sys

tree={}
np = -1

home=0
tree[home]=[None, None, None]

def search(p, x):
    while p != None:
        tmp = tree[p][0]
        if tmp == x: return True
        if x < tmp:
            p = tree[p][1]
        else:
            p = tree[p][2]
    return False

def node(x):
    global np
    np += 1
    tree[np] = [x, None, None]
    return np

def insert(p, x):
    if p == None or np == -1: return node(x)
    tmp = tree[p][0]
    if x== tmp: return p
    elif x<tmp:
        tree[p][1]=insert(tree[p][1],x)
    else:
        tree[p][2]=insert(tree[p][2],x)
    return p

def preorder(p):
    if p == None: return []
    p1, p2 = tree[p][1:3]
    return [tree[p][0]] + preorder(p1) + preorder(p2)

def inorder(p):
    if p == None: return []
    p1, p2 = tree[p][1:3]
    return inorder(p1) + [tree[p][0]] +inorder(p2)

n = int(input())
i = 0
while i<n:
    s = raw_input()
    if s[0]=='i':
        insert(home,int(s[7:]))
    elif s[0]=='p':
        print ' ' + ' '.join(map(str, inorder(home)))
        print ' ' + ' '.join(map(str, preorder(home)))
    i += 1

Submission status: Time Limit Exceeded

Solution code:
import sys

tree={}
np = -1

home=0
tree[home]=[None, None, None]

def search(p, x):
    while p != None:
        tmp = tree[p][0]
        if tmp == x: return True
        if x < tmp:
            p = tree[p][1]
        else:
            p = tree[p][2]
    return False

def node(x):
    global np
    np += 1
    tree[np] = [x, None, None]
    return np

def insert(p, x):
    if p == None or np == -1: return node(x)
    tmp = tree[p][0]
    if x== tmp: return p
    elif x<tmp:
        tree[p][1]=insert(tree[p][1],x)
    else:
        tree[p][2]=insert(tree[p][2],x)
    return p

def preorder(p):
    if p == None: return []
    p1, p2 = tree[p][1:3]
    return [tree[p][0]] + preorder(p1) + preorder(p2)

def inorder(p):
    if p == None: return []
    p1, p2 = tree[p][1:3]
    return inorder(p1) + [tree[p][0]] +inorder(p2)

n = int(input())
i = 0
while i<n:
    s = raw_input()
    if s[0]=='i':
        insert(0,int(s[7:]))
    elif s[0]=='p':
        print ' ' + ' '.join(map(str, inorder(home)))
        print ' ' + ' '.join(map(str, preorder(home)))
    i += 1

Submission status: Memory Limit Exceeded

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
input:
8
insert 30
insert 88
insert 12
insert 1
insert 20
insert 17
insert 25
print

4
insert 3
insert 2
insert 4
print

output: in_order + pre_order
1 12 17 20 25 30 88
30 12 1 20 17 25 88
"""

import sys


class Node(object):
    def __init__(self, data):
        self.data = data
        self.left, self.right = None, None
        self.pre_order = []

    def insert(self, data):
        """
        insert data according to BST rules
        """
        if data < self.data:
            if self.left is None:
                self.left = Node(data)
            else:
                self.left.insert(data)
        else:
            if self.right is None:
                self.right = Node(data)
            else:
                self.right.insert(data)

        return None

    def in_order_data(self, key):
        stack = []
        node = self
        while stack or node:
            if node:
                stack.append(node)
                if key.startswith('pr'):
                    yield node.data
                node = node.left
            else:
                node = stack.pop()
                if key.startswith('i'):
                    yield node.data
                node = node.right


def action(command, content):
    if command.startswith('in'):
        tree_root.insert(data=int(content))

    elif command.startswith('pr'):
        print('', *tree_root.in_order_data(key='in'))
        print('', *tree_root.in_order_data(key='pre'))

    return None


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    array_length = int(_input[0])
    command_list = list(map(lambda x: x.split(), _input[1:]))
    # assert len(command_list) == array_length
    # print(array_length, *command_list)

    flag, tree_root = True, None
    for each in command_list:
        command, content = each[0], each[-1]
        if flag and command.startswith('in'):
            tree_root = Node(data=int(content))
            flag = False
            continue
        action(command=command, content=content)