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
input = sys.stdin.readline
btree = []
root = None


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


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


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


def insert(key):
    global root
    z = Node(key, None, None, None)
    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  # zをyの左の子にする
    else:
        y.right = z  # zをyの右の子にする


def showtree(root):
    showInorder(root)
    print()
    showPreorder(root)
    print()


def main():
    m = int(input())
    global root
    for i in range(m):

        operation = input().split()

        # print(operation)

        if operation[0] == 'insert':
            # print("insert!")
            insert(int(operation[1]))
        else:
            # print("show tree!")
            # print("root.key:{0} root.left:{1} root.right:{2}".format(root.key, root.left, root.right))
            showtree(root)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class node:
    def __init__(self):
        self.p = -1
        self.l = -1
        self.r = -1

def preParse(u):
    if u == -1:
        return
    print(" " + str(u), end = '')
    preParse(T[u].l)
    preParse(T[u].r)

def inParse(u):
    if u == -1:
        return
    inParse(T[u].l)
    print(" " + str(u), end = '')
    inParse(T[u].r)

def postParse(u):
    if u == -1:
        return
    postParse(T[u].l)
    postParse(T[u].r)
    print(" " + str(u), end = '')

root = -1
def insert(T, z):
    global root
    parent = -1
    u = root
    while u != -1:
        parent = u
        if z < u:
            u = T[u].l
        else:
            u = T[u].r
    T[z].p = parent
    if parent == -1:
        root = z
    elif z < parent:
        T[parent].l = z
    else:
        T[parent].r = z


n = int(input())
cmdList = [input() for _ in range(n)]
T = {int(cmd[7:]): node() for cmd in cmdList if cmd[0] == "i"}

for cmd in cmdList:
    if cmd[0] == "p":
        inParse(root)
        print("")
        preParse(root)
        print("")
    else:
        insert(T, int(cmd[7:]))

Submission status: Accepted

Solution code:
class Node():
    """節クラス: valは節の値, parent/left/rightはそれぞれ親/左側の子/右側の子へのポインタを表す"""
    def __init__(self, val):
        self.val = val
        self.parent = None
        self.right = None
        self.left = None


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

    def search(self, val: int) -> bool:
        """二分木に値valを持つ節が存在するかどうか判定する
        根から順番に子を辿っていき、valと一致する節が存在する場合はTrue、存在しない場合はFalseを返す
        """
        ptr = self.root
        while ptr is not None:
            if ptr.val == val:
                return True
            if val < ptr.val:
                ptr = ptr.left
            else:
                ptr = ptr.right
        return False 

    def insert(self, val: int):
        """二分木に値valを持つ節を追加する（すでに二分木内に同じ要素が存在している場合も追加する）
        根から順番に子を辿っていき、ポインタが示す先に節が存在しなくなったらNode(val)として節を追加する
        """
        if self.root is None:
            # 二分木の根が存在しないときはrootに節を作る
            self.root = Node(val)
            return

        ptr = self.root 
        while True:
            if val < ptr.val:
                if ptr.left is None:
                    # ポインタの示す先に節が存在しない場合はNode(val)を追加する
                    ptr.left = Node(val)
                    ptr.left.parent = ptr
                    return
                ptr = ptr.left
            else:
                if ptr.right is None:
                    # ポインタの示す先に節が存在しない場合はNode(val)を追加する
                    ptr.right = Node(val)
                    ptr.right.parent = ptr
                    return
                ptr = ptr.right
        
    def delete(self, val: int):
        """二分木から値valを持つ節を削除する
        根から順番に子を辿っていき、ptr.val == val が見つかったらptrをつなぎ替える。
        """
        if self.root is None:
            # 二分木の根に節が存在しないときは何もしない
            return 
        
        ptr = self.root
        # ptr.val == valとなる節を探す             
        while True: 
            if ptr is None:
                return
            if ptr.val == val:
                break
            elif val < ptr.val:
                ptr = ptr.left
            else:
                ptr = ptr.right
       
        # 子が存在しないとき
        if ptr.left is None and ptr.right is None:
            if ptr.parent.left == ptr:
                ptr.parent.left = None
            else:
                ptr.parent.right = None
        # 子が右側にのみ存在するとき
        elif ptr.left is None:
            if ptr.parent.left == ptr:
                ptr.parent.left = ptr.right
                ptr.right.parent = ptr.parent
            else:
                ptr.parent.right = ptr.right
                ptr.right.parent = ptr.parent
        # 子が左側にのみ存在するとき
        elif ptr.right is None:
            if ptr.parent.left == ptr:
                ptr.parent.left = ptr.left
                ptr.left.parent = ptr.parent
            else:
                ptr.parent.right = ptr.left
                ptr.left.parent = ptr.parent
        # 子が両側にのみ存在するとき
        else:
            s = self.search_min(ptr.right)
            ptr.val = s.val
            if s.parent.left == s:
                s.parent.left = None
            else:
                s.parent.right = None            
    
    def search_min(self, ptr):
        """ptrを部分木の根としたときのptrの最小値の節へのポインタを返す
        ptr.leftをひたすら辿っていくことで可能"""
        while True:
            if ptr.left is None:
                return ptr
            ptr = ptr.left
            
    def rotate_left(self, ptr):
        """木を左回転する"""
        w = ptr.right
        w.parent = ptr.parent
        if w.parent is not None:
            if w.parent.left == ptr:
                w.parent.left = w
            else:
                w.parent.right = w
        ptr.right = w.left
        if ptr.right is not None:
            ptr.right.parent = ptr
        ptr.parent = w
        w.left = ptr
        if ptr == self.root:
            self.root = w
            self.root.parent = None

 
    def rotate_right(self, ptr):
        """木を右回転する"""
        w = ptr.left
        w.parent = ptr.parent
        if w.parent is not None:
            if w.parent.right == ptr:
                w.parent.right = w
            else:
                w.parent.left = w
        ptr.left = w.right
        if ptr.left is not None:
            ptr.left.parent = ptr
        ptr.parent = w
        w.right = ptr
        if ptr == self.root:
            self.root = w
            self.root.parent = None

    def preorder_tree_walk(self, ptr, res):
        """先行順巡回(preorder tree walk)"""
        if ptr is None:
            return res
        res.append(ptr.val)
        if ptr.left is not None:
            self.preorder_tree_walk(ptr.left, res)
        if ptr.right is not None:
            self.preorder_tree_walk(ptr.right, res)
        return res

    def inorder_tree_walk(self, ptr, res):
        """中間順巡回(inorder tree walk)"""
        if ptr is None:
            return res
        if ptr.left is not None:
            self.inorder_tree_walk(ptr.left, res)
        res.append(ptr.val)
        if ptr.right is not None:
            self.inorder_tree_walk(ptr.right, res)
        return res

    def postorder_tree_walk(self, ptr, res):
        """後行順巡回(postorder tree walk)"""
        if ptr is None:
            return res
        if ptr.left is not None:
            self.inorder_tree_walk(ptr.left, res)
        if ptr.right is not None:
            self.inorder_tree_walk(ptr.right, res)
        res.append(ptr.val)
        return res
      
      
n = int(input())
info = [list(input().split()) for i in range(n)]
bt = BinaryTree()

for i in range(n):
    if info[i][0] == "insert":
        bt.insert(int(info[i][1]))
    else:
        print(" ", end="")
        print(*bt.inorder_tree_walk(bt.root, res=[]))
        print(" ", end="")
        print(*bt.preorder_tree_walk(bt.root, res=[]))

Submission status: Accepted

Solution code:
num = int(input())
NIL = -1
MAX = 10000

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

class BST():
    def __init__(self):
        self.root = None
        self.In = []
        self.Pr = []
    
    def insert(self, data):
        n = self.root
        if n == None:
            self.root = Node(data)
            return 
        else:
            while True:
                entry = n.data
                if data < entry:
                    if n.left == None:
                        n.left = Node(data)
                        return
                    n = n.left
                elif data > entry:
                    if n.right == None:
                        n.right = Node(data)
                        return
                    n = n.right
                else:
                    n.data =data
                    return
                
    def inorder(self, node):
        if node != None:
            self.inorder(node.left)
            self.In.append(node.data)
            self.inorder(node.right)
        return self
    
    def preorder(self, node):
        if node != None:
            self.Pr.append(node.data)
            self.preorder(node.left)
            self.preorder(node.right)
        return self

a = BST()
for i in range(num):
    order = input().split()
    
    if order[0] == 'print':
        a.In = []
        a.Pr = []
        a.inorder(a.root)
        In = [str(j) for j in a.In]
        a.preorder(a.root)
        Pr = [str(j)  for j in a.Pr]
        print(' ' + ' '.join(In))
        print(' ' + ' '.join(Pr))
    else:
        order[1] = int(order[1])
        if i == 0:
            root = order[1]
        a.insert(order[1])

Submission status: Accepted

Solution code:
# https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/8/ALDS1_8_A
# 次への伏線みたいなもの
# ここらへんはもうひたすら実装するだけ
import sys
sys.setrecursionlimit(2**20)  # 再帰回数上限の向上 かなり多くしないとREになる


class Node:
    def __init__(self,
                 parent=None,
                 left=None,
                 right=None):
        self.parent = parent
        self.left = left  # 左の子ノード
        self.right = right  # 右の**子**


def pre_parse(T: dict, u: int, pre_ls: list):
    # 深さ優先探索特有の即時終了条件
    if u == None:
        return
    pre_ls.append(u)
    pre_parse(T, T[u].left, pre_ls)  # より左の方から深さ優先探索
    pre_parse(T, T[u].right, pre_ls)


def in_parse(T, u, in_ls):
    if u == None:
        return
    # 左→中→右っていうちょっと気持ち悪い順番
    in_parse(T, T[u].left, in_ls)
    in_ls.append(u)
    in_parse(T, T[u].right, in_ls)


def insert(T, ROOT, z):
    '''
    zは接点番号(そしてその接点番号が内容でもある)
    この接点番号を二分探索木の条件に従うように挿入する。
    '''
    # もしTが空だった場合(最初の一回しか発動されない)
    if ROOT == z:
        T[z] = Node()
    # もしTにいくつか入っていた場合
    else:
        T[z] = Node()  # 初期化
        x = ROOT
        while x is not None:  # 子がNoneになったらbreakする
            next_parent = x  # 次のループではxの親になる。whileから抜けたときに使用する
            if z < x:  # もし新たなノードが現在のノードよりも小さければ左に移動する
                x = T[x].left
            else:
                x = T[x].right
        T[z].parent = next_parent
        # 親の右と左どっちにつける？
        if z < next_parent:
            T[next_parent].left = z
        else:
            T[next_parent].right = z


def print_result(T):
    pre_ls, in_ls = [], []
    in_parse(T, ROOT, in_ls)
    pre_parse(T, ROOT, pre_ls)
    print('', *in_ls)
    print('', *pre_ls)


    # データの読み込み
N = int(input())
T = {}
for i in range(N):
    tmp = input()
    if tmp.startswith('print'):
        print_result(T)
    else:
        if len(tmp.split()) == 1:
            raise ValueError(tmp)
        command, z = tmp.split()[0], tmp.split()[1]
        z = int(z)
        if i == 0:
            ROOT = z
        insert(T, ROOT, z)

Submission status: Accepted

Solution code:
from typing import List, Optional


class Node:
	def __init__(self, key) -> None:
		self.key: int = key
		self.left: Optional[Node] = None
		self.right: Optional[Node] = None
		self.parent: Optional[Node] = None


class Tree:
	def __init__(self) -> None:
		self.root: Optional[Node] = None


def insert(T: Tree, z: Node) -> None:
	y: Optional[Node] = None
	x: Optional[Node] = T.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:
		T.root = z
	elif z.key < y.key:
		y.left = z
	else:
		y.right = z


def inorder(z: Optional[Node]):
	if z is not None:
		inorder(z.left)
		print(f" {z.key}", end="")
		inorder(z.right)


def preorder(z: Optional[Node]):
	if z is not None:
		print(f" {z.key}", end="")
		preorder(z.left)
		preorder(z.right)


if __name__ == "__main__":
	m = int(input())
	T = Tree()
	for _ in range(m):
		command = list(input().split())
		if command[0] == "insert":
			z = Node(int(command[1]))
			insert(T, z)
		else:
			inorder(T.root)
			print("")
			preorder(T.root)
			print("")

Submission status: Accepted

Solution code:
def preorder(T, index):
    print(" %d" %T[index][3], end="")
    if T[index][1] != -1:
        preorder(T, T[index][1])
    if T[index][2] != -1:
        preorder(T, T[index][2])


def inorder(T, index):
    if T[index][1] != -1:
        inorder(T, T[index][1])
    print(" %d" %T[index][3], end="")
    if T[index][2] != -1:
        inorder(T, T[index][2])

def insert(T, z):
    if len(T) == 0:
        T.append([0, -1, -1, z])
    else:
        i = 0
        T.append([0, -1, -1, z])
        while True:
            if T[i][3] > z and T[i][1] == -1:
                T[i][1] = len(T) - 1
                T[-1][0] = i
                break
            elif T[i][3] < z and T[i][2] == -1:
                T[i][2] = len(T) - 1
                T[-1][0] = i
                break
            elif T[i][3] > z:
                i = T[i][1]
            elif T[i][3] < z:
                i = T[i][2]


n = int(input())
a = [input().split() for _ in range(n)]

ans = []
for i in a:
    if i[0] == 'insert':
        insert(ans, int(i[1]))
    else:
        inorder(ans, 0)
        print("")
        preorder(ans, 0)
        print("")

Submission status: Accepted

Solution code:
import sys
from sys import stdin
input = stdin.readline

class BinaryTreeNode:
    def __init__(self, node):
        self.node = node
        self.left = None
        self.right = None

def Insert(parent, child):
    if parent.node > child.node:
        if parent.left != None:
            Insert(parent.left, child)
        else:
            parent.left = child
    else:
        if parent.right != None:
            Insert(parent.right, child)
        else:
            parent.right = child

IN_RESULT = []
def Inorder(root):
    if root.left == None:
        IN_RESULT.append(str(root.node))
        if root.right != None:
            Inorder(root.right)
    else:
        Inorder(root.left)
        IN_RESULT.append(str(root.node))
        if root.right != None:
            Inorder(root.right)
        else:
            pass
        
PRE_RESULT = []
def Preorder(root):
    PRE_RESULT.append(str(root.node))
    if root.left != None:
        Preorder(root.left)
    else:
        pass
    
    if root.right != None:
        Preorder(root.right)
    else:
        pass
    
    

n = int(input())


command = input()
if command[0] == "i":
    root = BinaryTreeNode(int(command[7:]))

for _ in range(n-1):
    command = input()
    if command[0] == "i":
        child = BinaryTreeNode(int(command[7:]))
        Insert(root, child)
        
    
    else:
        Inorder(root)
        Preorder(root)
        print(" "+" ".join(IN_RESULT))
        print(" "+" ".join(PRE_RESULT))
        IN_RESULT = []
        PRE_RESULT = []

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n = int(input())

Order = []
for _ in range(n):
    o = input().split()
    Order.append(o)

class Node:
    def __init__(self, key, value, left, right):
        self.key = key
        self.value = value
        self.left = left
        self.right = right
        
class BinaryTree:
    def __init__(self):
        self.root = None
        
    def insert(self, key, value):
        if self.root == None:
            node = Node(key, value, None, None)
            self.root = node
        else:
            node = Node(key, value, None, None)
            cmp_node = self.root
            while 1:
                if cmp_node.value > value and cmp_node.left == None:
                    cmp_node.left = node
                    break
                elif cmp_node.value > value and cmp_node.left != None:
                    cmp_node = cmp_node.left
                elif cmp_node.value < value and cmp_node.right == None:
                    cmp_node.right = node
                    break
                elif cmp_node.value < value and cmp_node.right != None:
                    cmp_node = cmp_node.right
        
def mid_search(node):
    if node == None:
        return
    mid_search(node.left)
    print('', node.key, end='')
    mid_search(node.right)
    
def fast_search(node):
    if node == None:
        return
    print('', node.key, end='')
    fast_search(node.left)
    fast_search(node.right)    
        
T = BinaryTree()
for o in Order:
    if o[0] == 'insert':
        T.insert(int(o[1]), int(o[1]))
    if o[0] == 'print':
        mid_search(T.root)
        print()
        fast_search(T.root)
        print()

Submission status: Accepted

Solution code:
# ALDS1_8_A Binary Search Tree 1
import sys


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


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

    def insert(self, x):
        new = Node(x)
        x_parent = self.root
        next = self.root

        while next is not None:
            x_parent = next
            if x < x_parent.key:
                next = x_parent.left
            else:
                next = x_parent.right

        if x_parent is None:
            self.root = new
        elif x < x_parent.key:
            new.parent = x_parent
            x_parent.left = new
        else:
            new.parent = x_parent
            x_parent.right = new
        return

    def preorder(self, node):
        print(' {}'.format(node.key), end='')

        if node.left:
            self.preorder(node.left)
        if node.right:
            self.preorder(node.right)
        return

    def inorder(self, node):
        if node.left:
            self.inorder(node.left)

        print(' {}'.format(node.key), end='')

        if node.right:
            self.inorder(node.right)


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

for i in range(m):
    command = list(sys.stdin.readline().strip().split())
    if command[0] == 'print':
        tree.inorder(tree.root)
        print()
        tree.preorder(tree.root)
        print()
    else:
        num = command[1]
        command = command[0]
        num = int(num)
        tree.insert(num)

Submission status: Accepted

Solution code:
class Node:

    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
        self.parent = None

    def append(self, node):
        if self.value > node.value:
            if self.left is None:
                node.parent = self
                self.left = node
            else:
                self.left.append(node)
        else:
            if self.right is None:
                node.parent = self
                self.right = node
            else:
                self.right.append(node)

    def in_parse(self, node, lst):
        if node is None:
            return
        self.in_parse(node.left, lst)
        lst.append(str(node.value))
        self.in_parse(node.right, lst)

    def pre_parse(self, node, lst):
        if node is None:
            return
        lst.append(str(node.value))
        self.pre_parse(node.left, lst)
        self.pre_parse(node.right, lst)


class BinaryTree:

    def __init__(self):
        self.root = None

    def insert(self, value):
        node = Node(value)
        if self.root is None:
            self.root = node
        else:
            self.root.append(node)

    def in_parse(self):
        lst = []
        self.root.in_parse(self.root, lst)
        return lst

    def pre_parse(self):
        lst = []
        self.root.pre_parse(self.root, lst)
        return lst


def main():
    n = int(input())
    tree = BinaryTree()

    for _ in range(n):
        line = input().split(' ')
        command = line[0]
        if command == 'insert':
            v = int(line[1])
            tree.insert(v)
        else:
            print(' ' + ' '.join(tree.in_parse()))
            print(' ' + ' '.join(tree.pre_parse()))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

class Node:
    __slots__ = ['value', 'parent', 'left', 'right']
    def __init__(self, value: int, parent: 'Node' = None):
        self.value = value
        self.parent = parent
        self.left: Node = None
        self.right: Node = None
    def inParse(self):
        if self.value == None:
            return
        if self.left != None:
            self.left.inParse()
        print(' {}'.format(self.value), end='')
        if self.right != None:
            self.right.inParse()
    def preParse(self):
        if self.value == None:
            return
        print(' {}'.format(self.value), end='')
        if self.left != None:
            self.left.preParse()
        if self.right != None:
            self.right.preParse()

class BinarySearchTree:
    __slots__ = ['root']
    def __init__(self):
        self.root: Node = None
    def insert(self, x: int):
        if self.root == None:
            self.root = Node(x)
            return
        parent, current = None, self.root
        while current:
            parent = current
            if x < current.value:
                current = current.left
            else:
                current = current.right
        if x < parent.value:
            parent.left = Node(x, parent)
        else:
            parent.right = Node(x, parent)

def main():
    tree = BinarySearchTree()
    n = int(input())
    for _ in range(n):
        inp = input()
        if inp[0] == 'i':
            com, num = inp.split()
            tree.insert(int(num))
        else:
            tree.root.inParse()
            print()
            tree.root.preParse()
            print()

if __name__=='__main__': main()

Submission status: Accepted

Solution code:
m = int(input())

l, r = {}, {}

def insertnode(num, x):
    """xには毎回rootを設定（rootから順に比較してし、適した場所に追加）"""
    if num < x:
        if x in l:
            if l[x] != 3000000000:
                insertnode(num, l[x])
            else:
                l[x] = num
                return
        else:
            l[x] = num
            return
    else:
        if x in r:
            if r[x] != 3000000000:
                insertnode(num, r[x])
            else:
                r[x] = num
                return
        else:
            r[x] = num
            return

def inorder(num):
    if num == 3000000000:
        return
    if num in l:
        inorder(l[num])
    else:
        l[num] = 3000000000
        inorder(l[num])
    print(' ' + str(num), end='')
    if num in r:
        inorder(r[num])
    else:
        r[num] = 3000000000
        inorder(r[num])

def preorder(num):
    if num == 3000000000:
        return
    print(' ' + str(num), end='')
    if num in l:
        preorder(l[num])
    else:
        l[num] = 3000000000
        preorder(l[num])
    if num in r:
        preorder(r[num])
    else:
        r[num] = 3000000000
        preorder(r[num])

for i in range(m):
    order = input()
    if i == 0:
        global root
        root = int(order[7:])
        continue
    if order[0] == 'i':
        num = int(order[7:])
        insertnode(num, root)
    else:
        inorder(root)
        print()
        preorder(root)
        print()

Submission status: Accepted

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

n = int(input())
root = None
for index in range(n):
    inputL = input().split()
    if inputL[0] == 'insert':
        if index == 0:
            root = binaryTreeNode(int(inputL[1]))
        else:
            def walkNode(node, val, parent):
                if node != None:
                    if node.val > val:
                        walkNode(node.left, val, node)
                    else:
                        walkNode(node.right, val, node)
                else:
                    if parent.val > val:
                        parent.left = binaryTreeNode(val)
                    else:
                        parent.right = binaryTreeNode(val)
            walkNode(root, int(inputL[1]), None)
    else:
        inL = [] 
        def lookNodeIn(node):
            if node != None:
                lookNodeIn(node.left)
                inL.append(node.val)
                lookNodeIn(node.right)
        lookNodeIn(root)
        preL = []
        def lookNodePre(node):
            if node != None:
                preL.append(node.val)
                lookNodePre(node.left)
                lookNodePre(node.right)
        lookNodePre(root)
        print(' '+' '.join(list(map(str, inL))))
        print(' '+' '.join(list(map(str, preL))))

Submission status: Accepted

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

def bst_insert(node, label):
    if node is None:
        return Node(label)
   
    elif label< node.label:
        node.left = bst_insert(node.left, label)
    else:
        node.right = bst_insert(node.right, label)
    return node


def bst_inorder(node):
    global In
    if (node.left is not None):
        bst_inorder(node.left)
    In.append(node.label)
    if (node.right is not None):
        bst_inorder(node.right)
    return

def bst_preorder(node):
    global Pre
    Pre.append(node.label)
    if (node.left is not None):
        bst_preorder(node.left)
    if (node.right is not None):
        bst_preorder(node.right)
    return 

n= int(input())
tree = None
for i in range(n):
    cmmd = list(input().split( ))
    if cmmd[0] == "insert":
        k =int(cmmd[1])
        tree = bst_insert(tree, k)
    else:
        In =[]
        bst_inorder(tree)
        print("",*In)
        Pre =[]
        bst_preorder(tree)
        print("",*Pre)