from __future__ import print_function
from sys import stdin

def printf(str, *args):
	print(str % args, end='')

class Node:
	def __init__(self):
		self.left = None
		self.data = 0
		self.right = None

def preorder(p):
	if p != None:
		printf("%3d)"%p.data)
		preorder(p.left)
		preorder(p.right)
	return 0

def inorder(p):
	if p != None:
		inorder(p.left)
		printf("%3d)"%p.data)
		inorder(p.right)
	return 0

def postorder(p):
	if p != None:
		postorder(p.left)
		postorder(p.right)
		printf("%3d)"%p.data)
	return 0

def insert(x, p):
	if p == None:
		p = Node()
		p.data = x
	elif x < p.data:
		p.left = insert(x, p.left)
	else:
		p.right = insert(x, p.right)
	return p

prn = None
printf("\n### Select number ###\n")
printf("1. 전위 탐방(preorder)			search\n")
printf("2. 중위 탐방(inorder)			search\n")
printf("3. 후위 탐방(postorder) 		search\n")
printf("4. insert\n")
printf("5. ######## end ########\n")
printf("먼저 4번을 선택해서 이진 트리를 만들고 그 이진 트리에서 탐방 하세요.\n")
printf("4번의 입력 형태는 4 5와 같은 형태로 계속 같은 방법을 이용해서 이진 트리를 만드세요.\n")

while True:
	values = stdin.readline().strip('\n').split()
	if len(values) > 0:
		ch = int(values[0])
		if ch == 1:
			preorder(prn)
		elif ch == 2:
			inorder(prn)
		elif ch == 3:
			postorder(prn)
		elif ch == 4:
			x = int(values[1])
			prn = insert(x,prn)
		elif ch == 5:
			break

printf("######## end ########\n")

stdin.readline()