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: Accepted

Solution code:
import sys


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

    def __str__(self):
        return "Not implemented yet."

    def __repr__(self):
        return self.__str__()


def insert(key, node):
    if key < node.key:
        if node.left is None:
            left_node = Node(key, node)
            node.left = left_node
        else:
            insert(key, node.left)
    else:
        if node.right is None:
            right_node = Node(key, node)
            node.right = right_node
        else:
            insert(key, node.right)


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


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


def main():
    lines = sys.stdin.readlines()
    root = Node()

    for order in lines[1:]:
        if order.startswith("insert"):
            command, key = order.strip().split(" ")
            key = int(key)
            if root.key is None:
                root.key = key
            else:
                insert(key, root)
        elif order.startswith("print"):
            print_inorder(root)
            print("")
            print_preorder(root)
            print("")

if __name__ == "__main__":
    main()

Submission status: Accepted

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

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))
    else:
        inorder_tree_walk(root)
        print()
        preorder_tree_walk(root)
        print()

Submission status: Accepted

Solution code:
def insert(tree,k):
    y = None
    x = tree
    z = {'key':k, 'parent':None, 'left':None, 'right':None}
    while x != None:
        y = x
        if x['key'] > k:
            x = x['left']
        else:
            x = x['right']
    z['parent'] = 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, int(c[7:]))
    elif c[0] == 'p':
        print '',
        middleorder(tree)
        print
        print '',
        preorder(tree)
        print

Submission status: Accepted

Solution code:
class Tree:
    root = None

    def insert(self, node):
        y = None
        x = self.root
        while x:
            y = x
            x = x.left if node.key < x.key else x.right

        if not y:
            self.root = node
        elif node.key < y.key:
            y.left = node
        else:
            y.right = node

    def print(self):
        print(' ', end='')
        print(*self.root.print_in())
        print(' ', end='')
        print(*self.root.print_pre())


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

    def print_pre(self):
        yield self.key
        if self.left:
            for k in self.left.print_pre(): yield k
        if self.right:
            for k in self.right.print_pre(): yield k

    def print_in(self):
        if self.left:
            for k in self.left.print_in(): yield k
        yield self.key
        if self.right:
            for k in self.right.print_in(): yield k


tree = Tree()
m = int(input())

while m:
    l = input().split()
    if len(l) == 2:
        tree.insert(Node(int(l[1])))
    else:
        tree.print()
    m -= 1

Submission status: Accepted

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 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())
  
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))
    else:
        inorder_walk(top)
        print()
        preorder_walk(top)
        print()

Submission status: Accepted

Solution code:
class BinarySearchTree:
    root = None
    def insert(self, k):
        y = None
        x = self.root
        z = Node(k)
        while x:
            y = x
            if z.k < x.k:
                x = x.l
            else:
                x = x.r
        z.p = y
        
        if y == None:
            self.root = z
        else:
            if z.k < y.k:
                y.l = z
            else:
                y.r = z
        
    def preParse(self, u):
        if u == None:
            return 
        print("", str(u.k), end = "")
        self.preParse(u.l)
        self.preParse(u.r)

    def inParse(self, u):
        if u == None:
            return 
        self.inParse(u.l)
        print("", str(u.k), end = "")
        self.inParse(u.r)

class Node: 
    def __init__(self, k):
        self.k = k
        self.p = None
        self.l = None
        self.r = None

if __name__ == '__main__':
    n = int(input().rstrip())
    x = BinarySearchTree()
    for i in range(n):
        com = input().rstrip()
        if com.startswith("insert"):
            k = int(com.split(" ")[1])
            x.insert(k)
        else:
            x.inParse(x.root)
            print()
            x.preParse(x.root)
            print()

Submission status: Accepted

Solution code:
class Tree():
    def __init__(self):
        self.root = None

    def insert(self, z):
        y = None
        x = self.root
        while x:
            y = x
            if z.key < x.key:
                x = x.left
            else:
                x = x.right
        z.p = y

        if not y:
            self.root = z
        elif z.key < y.key:
            y.left = z
        else:
            y.right = z

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


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

    def inorder(self):
        if self.left:
            self.left.inorder()
        print(" {}".format(self.key), end="")
        if self.right:
            self.right.inorder()

    def preorder(self):
        print(" {}".format(self.key), end="")
        if self.left:
            self.left.preorder()
        if self.right:
            self.right.preorder()


tree = Tree()
n = int(input())
for _ in range(n):
    cmd = input().split()
    if cmd[0] == "insert":
        tree.insert(Node(int(cmd[1])))
    else:
        tree.show()

Submission status: Accepted

Solution code:
class BinarySearchTree:
    def __init__(self):
        self.root = None
    def in_order_traversal(self):
        def _in_order_line(node):
            if node:
                _in_order_line(node.left)
                print(' {0}'.format(node.key), end = '')
                _in_order_line(node.right)
        _in_order_line(self.root)
        print('')
    def pre_order_traversal(self):
        def _pre_order_line(node):
            if node:
                print(' {0}'.format(node.key), end = '')
                _pre_order_line(node.left)
                _pre_order_line(node.right)
        _pre_order_line(self.root)
        print('')


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

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



import sys

t = BinarySearchTree()

m = sys.stdin.readline()

for i in sys.stdin.readlines():
    if i[0] == 'i':
        k = int(i[7:])
        n = Node(k)
        insert(t, n)
    else:
        t.in_order_traversal()
        t.pre_order_traversal()

Submission status: Accepted

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)

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:

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

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 pre_order(self, node):
		print(" {}".format(node.key), end = "")
		if node.left:
			self.pre_order(node.left)
		if node.right:
			self.pre_order(node.right)
	def in_order(self, node):
		if node.left:
			self.in_order(node.left)
		print(" {}".format(node.key), end = "")
		if node.right:
			self.in_order(node.right)
	def out(self):
		self.in_order(self.root)
		print("")
		self.pre_order(self.root)
		print("")

tree = Tree()
n = int(input())
for i in range(n):
	c = input().split()
	if c[0] == "insert":
		tree.insert(int(c[1]))
	else:
		tree.out()

Submission status: Accepted

Solution code:
import sys

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 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] == "i":
            insert(Node(int(line.split()[1])))
        else:
            In = []
            Pre = []
            inorderTreeWalk(root)
            print " " + " ".join(map(str, In))
            preorderTreeWalk(root)
            print " " + " ".join(map(str, Pre))

Submission status: Accepted

Solution code:
#coding:utf-8
#1_8_A
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

    def insert(self, node):
        y = None # set parent
        x = self.root
        while x is not None:
            y = x
            if node.key < x.key:
                x = x.left
            else:
                x = x.right
    
        if y is None:
            self.root = node
        elif node.key < y.key:
            y.left = node
        else:
            y.right = node

def inorder(node):
    if node is None:
        return
    inorder(node.left)
    print(" {}".format(node.key), end = "")
    inorder(node.right)

def preorder(node):
    if node is None:
        return
    print(" {}".format(node.key), end = "")
    preorder(node.left)
    preorder(node.right)

m = int(input())
t = Tree()
for i in range(m):
    cmd = input().split()
    if cmd[0] == 'insert':
        t.insert(Node(int(cmd[1])))
    else:
        inorder(t.root)
        print()
        preorder(t.root)
        print()

Submission status: Accepted

Solution code:
from collections import namedtuple
Node = namedtuple('Node', ['p', 'left', 'right'])

def insert(T, z):
    p = None
    x = T['root']
    while x != None:
        p = x
        if z < x: x = T[x].left
        else    : x = T[x].right

    T[z] = Node(p, None, None)

    if p == None:
        T['root'] = z
    elif z < p: T[p] = Node(T[p].p, z, T[p].right)
    else      : T[p] = Node(T[p].p, T[p].left, z)

 
def getInorderList(T, i):
    l = T[i].left
    r = T[i].right
    if l: yield from getInorderList(T, l)
    yield i
    if r: yield from getInorderList(T, r)


def getPreorderList(T, i):
    l = T[i].left
    r = T[i].right
    yield i
    if l: yield from getPreorderList(T, l)
    if r: yield from getPreorderList(T, r)


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

    T = {}
    T['root'] = None
    for _ in range(m):        
        op = input().split()
        if op[0] == 'insert': insert(T, int(op[1]))
        else:
            print("",*getInorderList(T, T['root']))
            print("",*getPreorderList(T, T['root']))

Submission status: Accepted

Solution code:
class BinarySearchTree:
    class Node:
        def __init__(self, k, p, left, right):
            self.key = k
            self.p = p
            self.left = left
            self.right = right
    def __init__(self):
        self.root = None
    def insert(self, k):
        p = None
        x = self.root
        while x != None:
            p = x
            if k < x.key : x = x.left
            else         : x = x.right
        z = self.Node(k, p, None, None)
        if p == None      : self.root = z
        elif z.key < p.key: p.left  = z
        else              : p.right = z
    def getInorderList(self, root):
        l = root.left
        r = root.right
        if l: yield from self.getInorderList(l)
        yield root.key
        if r: yield from self.getInorderList(r)
    def getPreorderList(self, root):
        l = root.left
        r = root.right
        yield root.key
        if l: yield from self.getPreorderList(l)
        if r: yield from self.getPreorderList(r)


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

    T = BinarySearchTree()
    for _ in range(m):        
        op = input().split()
        if   op[0] == 'insert': T.insert(int(op[1]))
        else:
            print("",*T.getInorderList(T.root))
            print("",*T.getPreorderList(T.root))

Submission status: Accepted

Solution code:
class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
        self.p = None
        
        
def insert(root, add):
    parent = None
    pCandidate = root
    while pCandidate is not None:
        parent = pCandidate
        if add.key < pCandidate.key:
            pCandidate = pCandidate.left
        else:
            pCandidate = pCandidate.right
    add.p = parent
    
    if parent is None:
        root = add
    elif add.key < parent.key:
        parent.left = add
    else:
        parent.right = add
    return root

def inorderTreeWalk(node):
    if node.left is not None:
        inorderTreeWalk(node.left)
    print(" {0}".format(node.key), end="")
    if node.right is not None:
        inorderTreeWalk(node.right)
        
def preorderTreeWalk(node):
    print(" {0}".format(node.key), end="")
    if node.left is not None:
        preorderTreeWalk(node.left)
    if node.right is not None:
        preorderTreeWalk(node.right)

n = int(input())
root = None
for i in range(n):
    line = input().split()
    if line[0] == "insert":
        root = insert(root, Node(int(line[1])))
    else:
        inorderTreeWalk(root)
        print()
        preorderTreeWalk(root)
        print()

Submission status: Accepted

Solution code:
import sys

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

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

    if y is None:
        return z
    else:
        if z.key < y.key:
            y.left = z
        else:
            y.right = z
        return t

def in_order(t):
    s = ""
    l = []
    curr = t
    while True:
        while curr is not None:
            l.append(curr)
            curr = curr.left
        if curr is None and len(l) == 0:
            break
        else:
            curr = l.pop()
            s += " " + str(curr.key)
            curr = curr.right
    return s

def pre_order(t):
    s = ""
    l = []
    curr = t
    while True:
        while curr is not None:
            s += " " + str(curr.key)
            l.append(curr)
            curr = curr.left
        if curr is None and len(l) == 0:
            break
        else:
            curr = l.pop()
            curr = curr.right
    return s

t = None
n = sys.stdin.readline()
lines = sys.stdin.readlines()
for line in lines:
    com = line.split()
    if com[0] == "insert":
        t = insert(t, Node(int(com[1])))
    else:
        print(in_order(t))
        print(pre_order(t))

Submission status: Accepted

Solution code:
import sys

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

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

    if y is None:
        return z
    else:
        if z.key < y.key:
            y.left = z
        else:
            y.right = z
        return t

def in_order(t):
    s = ""
    l = []
    curr = t
    while True:
        while curr is not None:
            l.append(curr)
            curr = curr.left
        if curr is None and len(l) == 0:
            break
        else:
            curr = l.pop()
            s += " " + str(curr.key)
            curr = curr.right
    return s

def pre_order(t):
    s = ""
    l = []
    curr = t
    while True:
        while curr is not None:
            s += " " + str(curr.key)
            l.append(curr)
            curr = curr.left
        if curr is None and len(l) == 0:
            break
        else:
            curr = l.pop()
            curr = curr.right
    return s

t = None
n = sys.stdin.readline()
lines = sys.stdin.readlines()
for line in lines:
    com = line.split()
    if line[0] == "i":
        t = insert(t, Node(int(com[1])))
    else:
        print(in_order(t))
        print(pre_order(t))

Submission status: Accepted

Solution code:
import sys
 
class Node():
    def __init__(self,key):
        self.key = key
        self.left = None
        self.right = None
 
def insert(t, z):
    y = None
    x = t
    while x is not None:
        y = x
        if z.key < x.key:
            x = x.left
        else:
            x = x.right
 
    if y is None:
        return z
    else:
        if z.key < y.key:
            y.left = z
        else:
            y.right = z
        return t
 
def in_order(t):
    s = ""
    l = []
    curr = t
    while True:
        while curr is not None:
            l.append(curr)
            curr = curr.left
        if curr is None and len(l) == 0:
            break
        else:
            curr = l.pop()
            s += " " + str(curr.key)
            curr = curr.right
    return s
 
def pre_order(t):
    s = ""
    l = []
    curr = t
    while True:
        while curr is not None:
            s += " " + str(curr.key)
            l.append(curr)
            curr = curr.left
        if curr is None and len(l) == 0:
            break
        else:
            curr = l.pop()
            curr = curr.right
    return s
 
t = None
n = sys.stdin.readline()
lines = sys.stdin.readlines()
for line in lines:
    com = line.split()
    if com[0] == "insert":
        t = insert(t, Node(int(com[1])))
    else:
        print(in_order(t))
        print(pre_order(t))

Submission status: Accepted

Solution code:
import sys
  
class Node():
    def __init__(self,key):
        self.key = key
        self.left = None
        self.right = None
  
def insert(t, z):
    y = None
    x = t
    while x is not None:
        y = x
        if z.key < x.key:
            x = x.left
        else:
            x = x.right
  
    if y is None:
        return z
    else:
        if z.key < y.key:
            y.left = z
        else:
            y.right = z
        return t
  
def inorder(t):
    s = ""
    l = []
    curr = t
    while True:
        while curr is not None:
            l.append(curr)
            curr = curr.left
        if curr is None and len(l) == 0:
            break
        else:
            curr = l.pop()
            s += " " + str(curr.key)
            curr = curr.right
    return s
  
def preorder(t):
    s = ""
    l = []
    curr = t
    while True:
        while curr is not None:
            s += " " + str(curr.key)
            l.append(curr)
            curr = curr.left
        if curr is None and len(l) == 0:
            break
        else:
            curr = l.pop()
            curr = curr.right
    return s
  
t = None
n = sys.stdin.readline()
lines = sys.stdin.readlines()
for line in lines:
    com = line.split()
    if com[0] == "insert":
        t = insert(t, Node(int(com[1])))
    else:
        print(inorder(t))
        print(preorder(t))

Submission status: Accepted

Solution code:
def insert(r, n):
    if 0 == len(T):
        T[n] = [None, None]
    else:
        if n < r:
            left = T[r][0]
            if left == None:
                T[r][0] = n
                T[n] = [None, None]
            else:
                insert(left, n)
        if r < n:
            right = T[r][1]
            if right == None:
                T[r][1] = n
                T[n] = [None, None]
            else:
                insert(right, n)

def print_inorder(r):
    left = T[r][0]
    right = T[r][1]
    ans = ""
    if left != None:
        ans += print_inorder(left)
    ans += " {}".format(r)
    if right != None:
        ans += print_inorder(right)
    return ans

def print_preorder(r):
    left = T[r][0]
    right = T[r][1]
    ans = " {}".format(r)
    if left != None:
        ans += print_preorder(left)
    if right != None:
        ans += print_preorder(right)
    return ans




n = int(input())
T = {}

root = None
for i in range(n):
    inst = input()
    if inst[0] == 'i':
        num = int(inst[7:])
        if i == 0:
            root = num
        insert(root, num)
    elif inst[0] == 'p':
        print(print_inorder(root))
        print(print_preorder(root))