Problem:
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 ≠ 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.

Solution (Python):
class binaryTree:
    def __init__(self,key,p=None,l=None,r=None):
        self.key = key
        self.p = p
        self.l = l
        self.r = r

N = int(input())
treelist = [list(input().split()) for i in range(N)]
root = None

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

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

    if y == None:
        root = z
    elif z.key < y.key:
        y.l = z
    else:
        y.r = z
    return root
    
def outorder(root):
    x = root
    if x == None:
        return
    global outlist
    outlist.append(x.key)
    
    outorder(x.l)
    outorder(x.r)

for data in treelist:
    if data[0] == "insert":
        z = binaryTree(int(data[1]))
        root = insert(root,z)
        
    if data[0] == "print":
        inlist = []
        outlist = []
        
        inorder(root)
        indata = " " + " ".join([str(num) for num in inlist])
        print(indata)
 
        outorder(root)
        outdata = " " + " ".join([str(num) for num in outlist])
        print(outdata)

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

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

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

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

    
    def printPreorder(self, parent): 
        print( " " + str(parent.key), end="" )
        if parent.left != None:
            self.printPreorder(parent.left)
        if parent.right != None:
            self.printPreorder(parent.right)

    
    def printInorder(self, parent): 
        if parent.left != None:
            self.printInorder(parent.left)
        print( " " + str(parent.key), end="" )
        if parent.right != None:
            self.printInorder(parent.right)

def main():
    T = Tree()
    Orders =[]
    tmp =[]
    N = int( input() )
    for i in range(N):
        tmp = [input().split()]
        Orders.extend( tmp )

    for order in Orders:
        if order[0] == "insert":
            T.insert( int( order[1] ) )
        elif order[0] == "print":
            T.printInorder( T.root )
            print("")
            T.printPreorder( T.root )
            print("")

if __name__ == '__main__':
    main()

Solution (Python):



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




class BinarySearch:
    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)


if __name__ == '__main__':

    n = int(input().rstrip())
    x = BinarySearch()

    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()

Solution (Python):

"""
Created on Thu Jul 19 22:51:44 2018

@author: maezawa
"""

class node():
    def __init__(self, key, parent=None, right=None, left=None):
        self.key = key
        self.parent = parent
        self.right = right
        self.left = left
        
def insert(z):
    global root
    y = None
    x = root
    while x != None:
        y = x
        if z.key < x.key:
            x = x.left
        else:
            x = x.right
    z.parent = y
    
    if y == None:
        root = z
    elif z.key < y.key:
        y.left = z
    else:
        y.right = z  
    
    
        
def inorder(u):
    if u == None:
        return
    inorder(u.left)
    print(' {}'.format(u.key), end = '')
    inorder(u.right)
    
def preorder(u):
    if u == None:
        return
    print(' {}'.format(u.key), end = '')
    preorder(u.left)
    preorder(u.right)
    
root = None

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

Solution (Python):
class Node:
	def __init__(self, k):
		self.k = k
		self.l = self.r = self.p = None
	def __str__(self):
		return str(self.k)

class BST:
	def __init__(self):
		self.root = None
	
	def insert(self, node):
		p = None
		cur = self.root
		while cur != None:
			p = cur
			if node.k < cur.k:
				cur = cur.l
			else:
				cur = cur.r
		node.p = p			
		if p == None:
			self.root = node
		elif node.k < p.k:
			p.l = node
		else:
			p.r = node
	
	def print(self):
		self.print_in_order()
		self.print_pre_order()
	
	def print_in_order(self):
		st = []
		cur = self.root
		while cur != None or len(st) != 0:
			if cur != None:
				st.append(cur)
				cur = cur.l
			else:
				cur = st.pop()
				print(' ' + str(cur), end='')
				cur = cur.r
		print()
		
	def print_pre_order(self):
		st = []
		st.append(self.root)
		while len(st) != 0:
			cur = st.pop()
			print(' ' + str(cur), end='')
			if cur.r != None:
				st.append(cur.r)
			if cur.l != None:
				st.append(cur.l)
		print()

m = int(input())
bst = BST()
for i in range(m):
	cmd = list(map(str, input().split()))
	if cmd[0] == 'insert':
		bst.insert(Node(int(cmd[1])))
	else:
		bst.print()

Solution (Python):


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]))
        preParseList = []
        inParseList = []

Solution (Python):
from io import StringIO
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
        self.output = StringIO()

    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

    def ini_print_inorder(self):
        self.output = StringIO()
        self.print_inorder(self.root)
        return self.output.getvalue()

    def ini_print_preorder(self):
        self.output = StringIO()
        self.print_preorder(self.root)
        return self.output.getvalue()

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

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

    def test_insert(self, keys):
        for k in keys:
            self.insert(k)

length = int(input())
b = BinaryTree()
for _ in range(length):
    comm = input()
    if comm[0] == "i":
        com, num = comm.split(" ")
        b.insert(int(num))
    else:
        print(" ", end = "")
        print((b.ini_print_inorder())[:-1])
        print(" ", end = "")
        print(b.ini_print_preorder()[:-1])

Solution (Python):
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 = 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, sorted(lis)))))
    print(" " + " ".join(list(map(str, lis))))

Solution (Python):
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, lis):
    
    if r != None:
      self.inorder(r.left, lis)
      lis.append(r.key)
      self.inorder(r.right, lis)


  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 = input().split()
  if query[0] == 'insert':
    bst.insert(int(query[1]))
  elif query[0] == 'print':
    root = bst.root
    in_lis = []
    pre_lis = []
    bst.preorder(root, pre_lis)
    bst.inorder(root, in_lis)
    print(" " + " ".join(list(map(str, in_lis))))
    print(" " + " ".join(list(map(str, pre_lis))))

Solution (Python):

"""
Created on Sat Mar  2 17:11:49 2019

@author: Yamazaki Kenichi
"""

m = int(input())
A = [list(input().split()) for i in range(m)]

T = [[-1,-1,-1,-1]]
def insert(T,u,x):
    if T[0][3] == -1:
        T[0][3] = x
        return
    if x < T[u][3]:
        if T[u][1] == -1:
            T[u][1] = len(T)
            T.append([u,-1,-1,x])
        else:
            insert(T,T[u][1],x)
    else:
        if T[u][2] == -1:
            T[u][2] = len(T)
            T.append([u,-1,-1,x])
        else:
            insert(T,T[u][2],x)
def ino(u):
    if T[u][1] != -1:
        ino(T[u][1])
    ino_res.append(str(T[u][3]))
    if T[u][2] != -1:
        ino(T[u][2])
def pre(u):
    pre_res.append(str(T[u][3]))
    if T[u][1] != -1:
        pre(T[u][1])
    if T[u][2] != -1:
        pre(T[u][2])
def find(u,x):
    if x == T[u][3]:
        return True
    elif x < T[u][3]:
        if T[u][1] == -1:
            return False
        return find(T[u][1],x)
    else:
        if T[u][2] == -1:
            return False
        return find(T[u][2],x)
for c in A:
    if c[0] == 'insert':
        insert(T,0,int(c[1]))
    elif c[0] == 'find':
        print('yes') if find(0,int(c[1])) else print('no')
    else:
        ino_res = []
        ino(0)
        pre_res = []
        pre(0)
        print(' '+' '.join(ino_res))
        print(' '+' '.join(pre_res))

Solution (Python):
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
        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 print_in_order(self, node):
        if node is None:
            return
        self.print_in_order(node.left)
        print(' ' + str(node.key), end='')
        self.print_in_order(node.right)

    def print_pre_order(self, node):
        if node is None:
            return
        print(' ' + str(node.key), end='')
        self.print_pre_order(node.left)
        self.print_pre_order(node.right)

tree = Tree()
m = int(input())
for i in range(m):
    line = input().split()
    if line[0] == 'print':
        tree.print_in_order(tree.root)
        print('')
        tree.print_pre_order(tree.root)
        print('')
    else:
        key = line[1]
        tree.insert(Node(int(key)))

Solution (Python):
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
            
            if node.key <= x.key:
                x = x.left
            else:
                x = x.right

        
        node.parent = p

        if p is None:
            self.root = node
        else:
            
            if node.key <= p.key:
                
                p.left = node
            else:
                
                p.right = node


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

    def print_preorder(self):
        self.preorder = []
        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))

Solution (Python):
class Node():
    def __init__(self, key):
        self.key = key
        self.left = self.right = None
        
def insert(key):
    global root

    x = root
    y = None
    while x:x, y = x.left if key < x.key else x.right , x
    if y == None:root = Node(key)
    elif y.key < key:y.right = Node(key)
    else:y.left = Node(key)
        
        
def pre(node):
    if node == None:return
    print('',node.key, end = '');pre(node.left);pre(node.right)
    
def ino(node):
    if node == None:return
    ino(node.left);print('',node.key,end='');ino(node.right)


n = int(input())
root = None
for j in range(n):
    s, *i = input().split()
    if s[0] == 'i':insert(int(i[0]))
    else:
        ino(root);print('');pre(root);print()

Solution (Python):
class Node():
    def __init__(self, key):
        self.key = key
        self.left = self.right = None
        
def insert(key):
    global root

    x = root
    y = None
    while x:x, y = x.left if key < x.key else x.right , x
    if y == None:root = Node(key)
    elif y.key < key:y.right = Node(key)
    else:y.left = Node(key)
        
        
def pre(node):
    if node == None:return
    print('',node.key, end = '');pre(node.left);pre(node.right)
    
def ino(node):
    if node == None:return
    ino(node.left);print('',node.key,end='');ino(node.right)


n = int(input())
root = None
for j in range(n):
    s, *i = input().split()
    if s[0] == 'i':insert(int(i[0]))
    else:
        ino(root);print();pre(root);print()

Solution (Python):
import sys
class Tree():
    def __init__(self):
        self.root = None
    def insert(self, key):
        z = Node(key)
        y = None
        x = self.root
        while x:
            y = x
            if z.key < x.key:
                x = x.left
            else:
                x = x.right
        z.parent = y
        if y == None:
            self.root = z
        elif z.key < y.key:
            y.left = z
        else:
            y.right = z
    def print(self):
        print('',' '.join(map(str, self.root.inwalk())))
        print('',' '.join(map(str, self.root.prewalk())))
    
class Node():
    def __init__(self, key):
        self.key = key
        self.parent = self.left = self.right = None
    def prewalk(self):
        ret = [self.key]
        if self.left:
            ret += self.left.prewalk()
        if self.right:
            ret += self.right.prewalk()
        return ret
    def inwalk(self):
        ret = []
        if self.left:
            ret += self.left.inwalk()
        ret += [self.key]
        if self.right:
            ret += self.right.inwalk()
        return ret
tree = Tree()
n = sys.stdin.readline()
for line in sys.stdin:
    if line[0] == 'i':
        tree.insert(int(line.split()[1]))
    else:
        tree.print()

Solution (Python):
import sys

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = self.right = None

class BST:
    def __init__(self):
        self.root = None
    
    def insert(self, node):
        def helper(root):
            y, x = None, root
            while isinstance(x, TreeNode):
                y = x
                if node.val < x.val:
                    x = x.left
                else:
                    x = x.right
            if y is None:
                root = node
            elif node.val < y.val:
                y.left = node
            else:
                y.right = node
            return root
            
        self.root = helper(self.root)
    
    def inorder(self):
        def helper(root):
            return [] if root is None else helper(root.left) + [root.val] + helper(root.right)
        return helper(self.root)

    def preorder(self):
        def helper(root):
            return [] if root is None else [root.val] + helper(root.left) + helper(root.right)
        return helper(self.root)

if __name__ == '__main__':
    q = sys.stdin.readline()
    q = int(q)
    bst = BST()
    for i in range(q):
        tmp = sys.stdin.readline()
        if tmp.startswith('print'):
            print ' ' + ' '.join(map(lambda x: str(x), bst.inorder()))
            print ' ' + ' '.join(map(lambda x: str(x), bst.preorder()))
        else:
            _, val = tmp.split()
            node = TreeNode(int(val))
            bst.insert(node)

Solution (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:])
        
        top = tree_insert(top, Node(key))
    else:
        inorder_walk(top)
        print()
        preorder_walk(top)
        print()

Solution (Python):
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()

Solution (Python):
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()

Solution (Python):
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

Solution (Python):
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

Solution (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:])
        
        top = tree_insert(top, Node(key))
    else:
        inorder_walk(top)
        print()
        preorder_walk(top)
        print()