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:


class Node(object):

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

        self.key = key


class Tree(object):

    def __init__(self):
        self.root = None

    def insert(self, new_key):
        x = self.root
        y = None

        while x is not None:
            y = x

            if new_key < y.key:
                x = y.left
            else:
                x = y.right

        new_node = Node(new_key)
        new_node.parent = y
        if y is None:
            self.root = new_node
        elif new_key < y.key:
            y.left = new_node
        else:
            y.right = new_node

    def inorder(self, now):
        visited = list()
        if now is None:
            return visited

        visited.extend(self.inorder(now.left))
        visited.append(now.key)
        visited.extend(self.inorder(now.right))
        return visited

    def preorder(self, now):
        visited = list()
        if now is None:
            return visited

        visited.append(now.key)
        visited.extend(self.preorder(now.left))
        visited.extend(self.preorder(now.right))
        return visited

    def order_print(self):
        keys = list()
        keys.append(self.inorder(self.root))
        keys.append(self.preorder(self.root))

        for visited_keys in keys:
            print "",
            print " ".join(map(str, visited_keys))

    def find(self, key):
        keys = self.inorder(self.root)
        if key in keys:
            print "yes"
        else:
            print "no"

    def min_node(self, now):
        """min_node
        Return the node with the minimum key,
        treeting now as the root of a sub tree.
        """
        if now.left is not None:
            return min_node(now.left)
        return now


    def delete(self, key):
        x = self.root
        y = None

        while x.key != key:
            y = x
            if key < y.key:
                x = y.left
            else:
                x = y.right

        # y is parent of x here
        if x.left is None and x.right is None:
            if y.left == x:
                y.left = None
            else:
                y.right = None
        elif x.left is None or x.right is None:
            child = x.left if x.left is not None else x.right
            child.parent = y
            if y.left == x:
                y.left = child
            else:
                y.right = child
        else:
            next_node = self.min_node(x.right)
            x.key = next_node.key
            self.delete(next_node)


def main():
    tree = Tree()

    num_orders = int(raw_input())
    for _ in xrange(num_orders):
        order = raw_input()
        if order[0] == 'i':
            new_key = int(order.split()[1])
            tree.insert(new_key)
        elif order[0] == 'p':
            tree.order_print()
        elif order[0] == 'f':
            key = int(order.split()[1])
            tree.find(key)
        elif order[0] == 'd':
            key = int(order.split()[1])
            tree.delete(key)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

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

class BinarySearchTree(list):
    def __init__(self):
        list.__init__(self)
        self.root = None
        
    def insert(self, z):
        z = Node(z)
        y = None
        x = self.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:
            self.root = z
        elif z.key < y.key:
            y.left = z
        else:
            y.right = z

    def preorder(self):
        def preParse(u):
            if u == None:
                return
            print(" " + str(u.key), end="")
            preParse(u.left)
            preParse(u.right)
        preParse(self.root)
        print("")

    def inorder(self):
        def inParse(u):
            if u == None:
                return
            inParse(u.left)
            print(" " + str(u.key), end="")
            inParse(u.right)
        inParse(self.root)
        print("")

if __name__ == '__main__':
    
    n = int(input())
    command = [input().split(" ") for _ in range(n)]
    T = BinarySearchTree()

    for c in command:
        if c[0] == "insert":
            T.insert(int(c[1]))
        else:
            T.inorder()
            T.preorder()

Submission status: Accepted

Solution code:
NIL = None
class Tree:
    def __init__(self, key = None):
        self.key = key
        self.p = NIL
        self.left = NIL
        self.right = NIL
n = int(input())
tree = {"root":NIL}
def insert(T, z):
    y = NIL
    x = T["root"]
    while x != NIL:
        y = x
        if z.key < x.key:
            x = x.left
        else:
            x = x.right
    z.p = y
    if y == NIL:
        T["root"] = z
    elif z.key < y.key:
        y.left = z
    else:
        y.right = z
def preorder_tree_walk(T):
    print(f" {T.key}", end="")
    if T.left != NIL:
        preorder_tree_walk(T.left)
    if T.right != NIL:
        preorder_tree_walk(T.right)
def inorder_tree_walk(T):
    if T.left != NIL:
        inorder_tree_walk(T.left)
    print(f" {T.key}", end="")
    if T.right != NIL:
        inorder_tree_walk(T.right)
for _ in range(n):
    ss = input()
    if ss[0] == "i":
        s, v = ss.split()
        insert(tree, Tree(int(v)))
    else:
        inorder_tree_walk(tree["root"])
        print()
        preorder_tree_walk(tree["root"])
        print()

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
NIL = None
class Tree:
    def __init__(self, key = None):
        self.key = key
        self.p = NIL
        self.left = NIL
        self.right = NIL
n = int(input())
tree = {"root":NIL}
def insert(T, z):
    y = NIL
    x = T["root"]
    while x != NIL:
        y = x
        if z.key < x.key:
            x = x.left
        else:
            x = x.right
    z.p = y
    if y == NIL:
        T["root"] = z
    elif z.key < y.key:
        y.left = z
    else:
        y.right = z
def preorder_tree_walk(T):
    print(f" {T.key}", end="")
    if T.left != NIL:
        preorder_tree_walk(T.left)
    if T.right != NIL:
        preorder_tree_walk(T.right)
def inorder_tree_walk(T):
    if T.left != NIL:
        inorder_tree_walk(T.left)
    print(f" {T.key}", end="")
    if T.right != NIL:
        inorder_tree_walk(T.right)
for _ in range(n):
    ss = readline()
    if ss[0] == "i":
        s, v = ss.split()
        insert(tree, Tree(int(v)))
    else:
        inorder_tree_walk(tree["root"])
        print()
        preorder_tree_walk(tree["root"])
        print()

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
NIL = None
class Tree:
    __slots__ = ['key', 'p', 'left', 'right']
    def __init__(self, key = None):
        self.key = key
        self.p = NIL
        self.left = NIL
        self.right = NIL
n = int(input())
tree = {"root":NIL}
def insert(T, z):
    y = NIL
    x = T["root"]
    while x != NIL:
        y = x
        if z.key < x.key:
            x = x.left
        else:
            x = x.right
    z.p = y
    if y == NIL:
        T["root"] = z
    elif z.key < y.key:
        y.left = z
    else:
        y.right = z
def preorder_tree_walk(T):
    print(f" {T.key}", end="")
    if T.left != NIL:
        preorder_tree_walk(T.left)
    if T.right != NIL:
        preorder_tree_walk(T.right)
def inorder_tree_walk(T):
    if T.left != NIL:
        inorder_tree_walk(T.left)
    print(f" {T.key}", end="")
    if T.right != NIL:
        inorder_tree_walk(T.right)
for _ in range(n):
    ss = readline()
    if ss[0] == "i":
        s, v = ss.split()
        insert(tree, Tree(int(v)))
    else:
        inorder_tree_walk(tree["root"])
        print()
        preorder_tree_walk(tree["root"])
        print()

Submission status: Accepted

Solution code:
import collections
sent = -1

def insert(hoge, new_node, root):
    #print(hoge)
    parent_maybe = sent
    now_looking = root
    hoge[new_node]['node_id'] = new_node
    while now_looking != sent:
        parent_maybe = now_looking
        if new_node < hoge[now_looking]['node_id']:
            now_looking = hoge[now_looking]['left']
        else:
            now_looking = hoge[now_looking]['right']
    hoge[new_node]['parent'] = parent_maybe
    
    if parent_maybe == sent:
        root = new_node
        hoge[new_node]['parent'] = sent
        hoge[new_node]['left'] = sent
        hoge[new_node]['right'] = sent
    elif new_node < hoge[parent_maybe]['node_id']:
        hoge[parent_maybe]['left'] = new_node
        hoge[new_node]['left'] = sent
        hoge[new_node]['right'] = sent
    else:
        hoge[parent_maybe]['right'] = new_node
        hoge[new_node]['left'] = sent
        hoge[new_node]['right'] =sent
    
    return root
    
def inorder(node_id):
    if node_id == sent:
        return None
    inorder(hoge[node_id]['left'])
    print(' {}'.format(node_id), end='')
    inorder(hoge[node_id]['right'])

def preorder(node_id):
    if node_id == sent:
        return None
    print(' {}'.format(node_id), end='')
    preorder(hoge[node_id]['left'])
    preorder(hoge[node_id]['right'])
    
    
def getTree(root):
    inorder(root)
    print()
    preorder(root)
    print()

if __name__ == '__main__':
    num = int(input())
    hoge = collections.defaultdict(dict)
    root = -1
    for _ in range(num):
        command = input()
        if command.split()[0] == 'insert':
            root = insert(hoge, int(command.split()[1]), root)
        else:
            getTree(root)

Submission status: Accepted

Solution code:
'''ALDS1_8_A: Binary search trees - Binary Search Tree I
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_8_A
******
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≤x.key. If y is a node in the right subtree of x, then x.key≤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. TT 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 kk 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 ≤500,001
- The number of print operations ≤10.
- −2,000,000,000≤key≤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.
******
＜方針１＞
    「__slots__」について
        Pythonではデフォルトではオブジェクトのインスタンスの属性はdictを使って保存している
        この保存の仕方では、実行中に新たな属性を動的に設定できたりして良い
        だけど、少数の固定な属性を持つ小さなクラスを扱うときにはdictはメモリの無駄
        こういう時は__slots__に属性の名前を記述することでメモリを節約したほうが良い
'''
import sys

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

class BST:
    def __init__(self):
        self.root = None
    def insert(self, key):
        x = self.root
        y = None
        z = Node(key)
        while x != None:
            y = x
            x = x.left if z.key < x.key else x.right
        if y == None: self.root = z
        else:
            if z.key < y.key: y.left = z
            else: y.right = z
    def print_tree(self):
        def inorder(node):
            if node:
                inorder(node.left)
                print('',node.key, end='')
                inorder(node.right)
        def preorder(node):
            if node:
                print('',node.key, end='')
                preorder(node.left)
                preorder(node.right)
        inorder(self.root)
        print()
        preorder(self.root)
        print()

tree = BST()
for e in [0]*int(input()):
    e = input()
    if e[0] == 'i': tree.insert(int(e[7:]))
    else:
        tree.print_tree()

Submission status: Accepted

Solution code:
class Node:
    __slots__ = ['key', 'left', 'right']
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None

class BST:
    def __init__(self):
        self.root = None
    def insert(self, key):
        x = self.root
        y = None
        z = Node(key)
        while x != None:
            y = x
            x = x.left if z.key < x.key else x.right
        if y == None: self.root = z
        else:
            if z.key < y.key: y.left = z
            else: y.right = z
    def print_tree(self):
        def inorder(node):
            if node:
                inorder(node.left)
                print('',node.key, end='')
                inorder(node.right)
        def preorder(node):
            if node:
                print('',node.key, end='')
                preorder(node.left)
                preorder(node.right)
        inorder(self.root)
        print()
        preorder(self.root)
        print()

tree = BST()
for e in [0]*int(input()):
    e = input()
    if e[0] == 'i': tree.insert(int(e[7:]))
    else:
        tree.print_tree()

Submission status: Accepted

Solution code:
import sys

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

class BST:
    def __init__(self):
        self.root = None
    def insert(self, key):
        x = self.root
        y = None
        z = Node(key)
        while x != None:
            y = x
            x = x.left if z.key < x.key else x.right
        if y == None: self.root = z
        else:
            if z.key < y.key: y.left = z
            else: y.right = z
    def print_tree(self):
        def inorder(node):
            if node:
                inorder(node.left)
                print('',node.key, end='')
                inorder(node.right)
        def preorder(node):
            if node:
                print('',node.key, end='')
                preorder(node.left)
                preorder(node.right)
        inorder(self.root)
        print()
        preorder(self.root)
        print()

tree = BST()
input()
for e in sys.stdin:
    if e[0] == 'i': tree.insert(int(e[7:]))
    else:
        tree.print_tree()

Submission status: Accepted

Solution code:
import sys

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

class BST:
    def __init__(self):
        self.root = None
    def insert(self, key):
        x = self.root
        y = None
        z = Node(key)
        while x != None:
            y = x
            x = x.left if z.key < x.key else x.right
        if y == None: self.root = z
        else:
            if z.key < y.key: y.left = z
            else: y.right = z
    def print_tree(self):
        def inorder(node):
            return inorder(node.left) + f' {node.key}' + inorder(node.right) if node else ''
        def preorder(node):
            return f' {node.key}' + preorder(node.left) + preorder(node.right) if node else ''
        print(inorder(self.root))
        print(preorder(self.root))

tree = BST()
input()
for e in sys.stdin:
    if e[0] == 'i': tree.insert(int(e[7:]))
    else: tree.print_tree()

Submission status: Accepted

Solution code:
import sys

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

class BST:
    def __init__(self):
        self.root = None
    def insert(self, key):
        x, y, z = self.root, None, Node(key)
        while x != None: x, y = x.left if z.key < x.key else x.right, x
        if y == None: self.root = z
        elif z.key < y.key: y.left = z
        else: y.right = z
    def print_tree(self):
        def inorder(node):
            return inorder(node.left) + f' {node.key}' + inorder(node.right) if node else ''
        def preorder(node):
            return f' {node.key}' + preorder(node.left) + preorder(node.right) if node else ''
        print(inorder(self.root))
        print(preorder(self.root))

tree = BST()
input()
for e in sys.stdin:
    if e[0] == 'i': tree.insert(int(e[7:]))
    else: tree.print_tree()

Submission status: Accepted

Solution code:
# 04:58 sec    63276 KB     912 bytes
import sys

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

class BST:
    def __init__(self):
        self.root = None
    def insert(self, key):
        x, y, z = self.root, None, Node(key)
        while x != None: x, y = x.left if z.key < x.key else x.right, x
        if y == None: self.root = z
        else:
            if z.key < y.key: y.left = z
            else: y.right = z
    def print_tree(self):
        def inorder(node):
            return inorder(node.left) + f' {node.key}' + inorder(node.right) if node else ''
        def preorder(node):
            return f' {node.key}' + preorder(node.left) + preorder(node.right) if node else ''
        print(inorder(self.root))
        print(preorder(self.root))

tree = BST()
input()
for e in sys.stdin:
    if e[0] == 'i': tree.insert(int(e[7:]))
    else: tree.print_tree()

Submission status: Accepted

Solution code:
import sys

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

class BST:
    def __init__(self):
        self.root = None
    def insert(self, key):
        x, y = self.root, None
        while x != None: x, y = x.left if key < x.key else x.right, x
        if y == None: self.root = Node(key)
        elif key < y.key: y.left = Node(key)
        else: y.right = Node(key)
    def print_tree(self):
        def inorder(node):
            return inorder(node.left) + f' {node.key}' + inorder(node.right) if node else ''
        def preorder(node):
            return f' {node.key}' + preorder(node.left) + preorder(node.right) if node else ''
        print(inorder(self.root))
        print(preorder(self.root))

tree = BST()
input()
for e in sys.stdin:
    if e[0] == 'i': tree.insert(int(e[7:]))
    else: tree.print_tree()

Submission status: Accepted

Solution code:
import sys

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

root = None

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

def inorder(node):
    return inorder(node.left) + f' {node.key}' + inorder(node.right) if node else ''
def preorder(node):
    return f' {node.key}' + preorder(node.left) + preorder(node.right) if node else ''

input()
for e in sys.stdin:
    if e[0] == 'i': insert(int(e[7:]))
    else:
        print(inorder(root))
        print(preorder(root))

Submission status: Accepted

Solution code:
import sys

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

root = None

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

def inorder(node):
    return inorder(node.left) + f' {node.key}' + inorder(node.right) if node else ''
def preorder(node):
    return f' {node.key}' + preorder(node.left) + preorder(node.right) if node else ''

input()
for e in sys.stdin:
    if e[0] == 'i': insert(int(e[7:]))
    else: print(inorder(root)); print(preorder(root))

Submission status: Accepted

Solution code:
import sys

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

class BST:
    def __init__(self):
        self.root = None
    def insert(self, key):
        x, y = self.root, None
        while x != None: x, y = x.left if key < x.key else x.right, x
        if y == None: self.root = Node(key)
        elif key < y.key: y.left = Node(key)
        else: y.right = Node(key)
    def print_tree(self):
        def inorder(node):
            return inorder(node.left) + f' {node.key}' + inorder(node.right) if node else ''
        def preorder(node):
            return f' {node.key}' + preorder(node.left) + preorder(node.right) if node else ''
        print(inorder(self.root))
        print(preorder(self.root))

tree = BST()
input()
for e in sys.stdin:
    if e[0] == 'i': tree.insert(int(e[7:]))
    else: tree.print_tree()

Submission status: Accepted

Solution code:
import sys

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

class BST:
    __slots__ = ['root']
    def __init__(self):
        self.root = None
    def insert(self, key):
        x, y = self.root, None
        while x != None: x, y = x.left if key < x.key else x.right, x
        if y == None: self.root = Node(key)
        elif key < y.key: y.left = Node(key)
        else: y.right = Node(key)
    def print_tree(self):
        def inorder(node):
            return inorder(node.left) + f' {node.key}' + inorder(node.right) if node else ''
        def preorder(node):
            return f' {node.key}' + preorder(node.left) + preorder(node.right) if node else ''
        print(inorder(self.root))
        print(preorder(self.root))

tree = BST()
input()
for e in sys.stdin:
    if e[0] == 'i': tree.insert(int(e[7:]))
    else: tree.print_tree()

Submission status: Accepted

Solution code:
import sys

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

root = None

def insert(key):
    global root
    x, y = root, None
    while x is not None: x, y = x.left if key < x.key else x.right, x
    if y is None: root = Node(key)
    elif key < y.key: y.left = Node(key)
    else: y.right = Node(key)

def inorder(node):
    return inorder(node.left) + f' {node.key}' + inorder(node.right) if node else ''
def preorder(node):
    return f' {node.key}' + preorder(node.left) + preorder(node.right) if node else ''

input()
for e in sys.stdin:
    if e[0] == 'i': insert(int(e[7:]))
    else: print(inorder(root)); print(preorder(root))

Submission status: Accepted

Solution code:
import sys

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

root = None

def insert(key):
    global root
    x, y = root, None
    while x: x, y = x.left if key < x.key else x.right, x
    if y is None: root = Node(key)
    elif key < y.key: y.left = Node(key)
    else: y.right = Node(key)

def inorder(node):
    return inorder(node.left) + f' {node.key}' + inorder(node.right) if node else ''
def preorder(node):
    return f' {node.key}' + preorder(node.left) + preorder(node.right) if node else ''

input()
for e in sys.stdin:
    if e[0] == 'i': insert(int(e[7:]))
    else: print(inorder(root)); print(preorder(root))

Submission status: Accepted

Solution code:
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 = int(input())
for i in range(n):
    com = input().split()
    if len(com) == 2:
        tree.insert(int(com[1]))
    else:
        tree.print()