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():
    def __init__(self, key, p, l, r):
        self.key, self.p, self.l, self.r = key, p, l, r


class BinarySearchTree():
    def __init__(self):
        self.tree = []
        self.root = -1

    def insert(self, key):
        y = -1  # parent of x
        x = self.root
        while x != -1:
            y = x
            if key < self.tree[x].key:
                x = self.tree[x].l
            else:
                x = self.tree[x].r
        self.tree.append(Node(key, y, -1, -1))
        z = len(self.tree) - 1
        if y == -1:
            self.root = z
        elif key < self.tree[y].key:
            self.tree[y].l = z
        else:
            self.tree[y].r = z

    def preorder_traversal(self, u):
        if u == -1:
            return
        print(' ' + str(self.tree[u].key), end='')
        self.preorder_traversal(self.tree[u].l)
        self.preorder_traversal(self.tree[u].r)

    def inorder_traversal(self, u):
        if u == -1:
            return
        self.inorder_traversal(self.tree[u].l)
        print(' ' + str(self.tree[u].key), end='')
        self.inorder_traversal(self.tree[u].r)


def main():
    n = int(input())
    bst = BinarySearchTree()
    for _ in range(n):
        order = input().split()
        if order[0] == 'insert':
            key = int(order[1])
            bst.insert(key)
        elif order[0] == 'print':
            bst.inorder_traversal(0)
            print('')
            bst.preorder_traversal(0)
            print('')


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

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


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

    return T


def preorder(T, ret):
    ret.append(T.key)

    if T.left is not None:
        preorder(T.left, ret)

    if T.right is not None:
        preorder(T.right, ret)


def inorder(T, ret):
    if T.left is not None:
        inorder(T.left, ret)

    ret.append(T.key)

    if T.right is not None:
        inorder(T.right, ret)


def main():
    m = int(input())
    Tree = None
    for i in range(m):
        cmd, *v = input().split()
        if cmd == "print":
            print(" ", end="")
            inans = []
            inorder(Tree, inans)
            print(*inans)
            print(" ", end="")
            preans = []
            preorder(Tree, preans)
            print(*preans)
        else:
            z = int(v[0])
            znode = Node(z)
            Tree = insert(Tree, znode)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class Node():
    def __init__(self,key):
        self.key = key
        self.parent = None
        self.left = None
        self.right = None
    def __str__(self):
        return str(self.key)
def inorder(r): ##r:root
    if (r.left != None):
        inorder(r.left)
    print(' ' + str(r.key), end ='')
    if (r.right != None):
        inorder(r.right)
def preorder(r):  ##r:root 
    print(" "+str(r.key), end ='')  ##preorder은 루트 쪽부터 print
    if (r.left != None):  ##left쪽으로 쭉감
        preorder(r.left) ##ns[i].left를 root로써 재귀함수!
    if (r.right != None):
        preorder(r.right) ##left다했으면 right으로도 똑같이 해줌 
root = None
def insert(z,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 z.key < y.key:
        y.left = z
    else:
        y.right = z
n = int(input())
command = str(input())
if command[0]=="i":
    root = Node(int(command[7:]))
else:
    print()
for i in range(n-1):
    com = str(input())
    if com[0] == "i":
        insert(Node(int(com[7:])),root)
    else:
        inorder(root)
        print()
        preorder(root)
        print()

Submission status: Accepted

Solution code:
from typing import Optional


class Node:
    def __init__(self, arg_parent: Optional["Node"], arg_key: int,
                 arg_left: Optional["Node"], arg_right: Optional["Node"]):
        self.parent = arg_parent
        self.key = arg_key
        self.left = arg_left
        self.right = arg_right


def print_preorder(node: Node) -> None:
    print(f" {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: Node) -> None:
    if node.left is not None:
        print_inorder(node.left)
    print(f" {node.key}", end="")
    if node.right is not None:
        print_inorder(node.right)


def insert(root: Optional[Node], node: Node) -> Node:
    y: Optional[Node] = None
    x = root

    while x is not None:
        y = x
        if node.key < x.key:
            x = x.left
        else:
            x = x.right
    node.parent = y

    if y is None:
        root = node
    elif node.key < y.key:
        y.left = node
    else:
        y.right = node

    assert root is not None
    return root


if __name__ == "__main__":
    root: Optional[Node] = None
    node_num = int(input())
    for _ in range(node_num):
        command, *value = input().split()
        if "insert" == command:
            root = insert(root, Node(None, int(value[0]), None, None))
        elif "print" == command:
            assert root is not None
            print_inorder(root)
            print()
            print_preorder(root)
            print()
        else:
            pass

Submission status: Accepted

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

parent_node = None

        
def getParent():
    tmp_node = Nodes
    while Nodes.parent != None:
        tmp_node = tmp_node.parent
    return tmp_node    

def printPreorder(u):
    if u == None:
        return
    print(" ", u.key, sep="", end="")
    printPreorder(u.left)
    printPreorder(u.right)
    
def printInorder(u):
    if u == None:
        return
    printInorder(u.left)
    print(" ", u.key, sep="", end="")
    printInorder(u.right)

n = int(input())

# メモリの確保
Nodes = []
for i in range(n):
    tmp_node = Node(0)
    Nodes.append(tmp_node)

for i in range(n):
    cmd = input().split()
    if cmd[0] == 'insert':
        key = int(cmd[1])

        insert_node = Nodes[i]
        insert_node.key = key
        key_parent = None
        x = parent_node
            
        while x != None:
            key_parent = x
            if insert_node.key < x.key:
                x = x.left
            else:
                x = x.right
        insert_node.parent = key_parent
            
        if key_parent == None:
            parent_node = insert_node
        elif insert_node.key < key_parent.key:
            key_parent.left = insert_node
        else:
            key_parent.right = insert_node
        # printInorder(parent_node)
        # print("")
        # printPreorder(parent_node)
        # print("")
    else:
        printInorder(parent_node)
        print("")
        printPreorder(parent_node)
        print("")

Submission status: Accepted

Solution code:
root = None

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

def preorder(T):
    if T is None:
        return
    print(' ' + str(T.key), end='')
    preorder(T.left)
    preorder(T.right)

def inorder(T):
    if T is None:
        return
    inorder(T.left)
    print(' ' + str(T.key), end='')
    inorder(T.right)

def find(T, z):
    if T is None:
        return False
    if T.key == z:
        return True

    if z < T.key and T.left is not None:
        return find(T.left, z)
    elif z > T.key and T.right is not None:
        return find(T.right, z)
    else:
        return False

def insert(T, z):
    global root
    if T is None:
        root = Node(z, None, None)
        return

    # print("\n# Insert: " + str(z))
    # print("# T: " + str(T.key))

    parent = T
    while True:
        if parent.left is None and parent.right is None:
            break
        elif parent.left is None and z < parent.key:
            break
        elif parent.right is None and z > parent.key:
            break

        # print("# left: " + str(parent.left.key))
        # print("# right: " + str(parent.right.key))

        if z < parent.key:
            parent = parent.left
#            print("# Slide parent to left: " + str(parent.key))
        else:
            parent = parent.right
#            print("# Slide parent to right: " + str(parent.key))

    if z < parent.key:
        node = Node(z, None, None)
        parent.left = node
    elif z > parent.key:
        node = Node(z, None, None)
        parent.right = node

n = int(input())

for i in range(n):
    s = input().split()
    if s[0] == 'insert':
        insert(root, int(s[1]))
    elif s[0] == 'find':
        if find(root, int(s[1])):
            print('yes')
        else:
            print('no')
    else:
        inorder(root)
        print('')
        preorder(root)
        print('')

Submission status: Accepted

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

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

    def insert(self, v):
        x = TreeNode(v)
        if not self.root:
            self.root = x
            return

        r = self.root
        while r is not None:
            parent = r
            if x.val < r.val:
                r = r.left
            else:
                r = r.right

        if x.val < parent.val:
            parent.left = x
        else:
            parent.right = x

    def in_order(self):
        def helper(node):
            if not node:
                return
            helper(node.left)
            res.append(node.val)
            helper(node.right)

        res = []
        helper(self.root)
        return res

    def pre_order(self):
        def helper(node):
            if not node:
                return
            res.append(node.val)
            helper(node.left)
            helper(node.right)

        res = []
        helper(self.root)
        return res


test = BST()
n = int(input())
for _ in range(n):
    order = input()
    if order.startswith("insert"):
        i, x = order.split()
        test.insert(int(x))
    else:
        print(" ",end="")
        print(*test.in_order())
        print(" ",end="")
        print(*test.pre_order())

Submission status: Accepted

Solution code:
NIL = -1


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


class BinaryTree():
    def __init__(self, node):
        self.root = node

    def insert(self, key):
        if self.root.key == NIL:
            self.root.key = key
            return

        now = self.root
        while now != NIL:
            parent = now
            if   key < now.key:
                now = now.left
            elif key > now.key:
                now = now.right
            else:
                raise
        
        insert = Node(key, parent)

        if   insert.key < parent.key:
            parent.left = insert
        elif insert.key > parent.key:
            parent.right = insert
        else:
            raise

    def treewalk_inorder(self, node):
        if isinstance(node, int):
            return

        self.treewalk_inorder(node.left)
        print(f" {node.key}", end="")
        self.treewalk_inorder(node.right)

    def treewalk_preorder(self, node):
        if isinstance(node, int):
            return

        print(f" {node.key}", end="")
        self.treewalk_preorder(node.left)
        self.treewalk_preorder(node.right)



n = int(input())

root_node = Node()
binary_tree = BinaryTree(root_node)


for _ in range(n):

    command, *list_num = input().split()

    if   command == "insert":
        k = int(list_num[0])
        binary_tree.insert(k)
    elif command == "print":
        binary_tree.treewalk_inorder(root_node)
        print()
        binary_tree.treewalk_preorder(root_node)
        print()
    else:
        raise

Submission status: Accepted

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

    def isRoot(self):
        return self.parent is None

    def preorder(self, arr):
        arr.append(str(self.id))
        if self.left is not None:
            self.left.preorder(arr)
        if self.right is not None:
            self.right.preorder(arr)

    def inorder(self, arr):
        if self.left is not None:
            self.left.inorder(arr)
        arr.append(str(self.id))
        if self.right is not None:
            self.right.inorder(arr)

    def postorder(self, arr):
        if self.left is not None:
            self.left.postorder(arr)
        if self.right is not None:
            self.right.postorder(arr)
        arr.append(str(self.id))

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

    z.parent = y

    if z.id < y.id:
        y.left = z
    else:
        y.right = z


m = int(input())
root = None

for i in range(m):
    arr = input().split()
    if arr[0] == 'print':
        arr = []
        root.inorder(arr)
        print('', ' '.join(arr))
        arr = []
        root.preorder(arr)
        print('', ' '.join(arr))
        continue

    id = int(arr[1])
    if root is None:
        root = Node(id)
        continue

    insert(root, Node(id))

Submission status: Accepted

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

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

    def insert(self, data):
        p = None # parent
        n = self.root
        if n == None:
            self.root = Node(data)
            return
        else:
            while n is not None:
                p = n
                if data < n.data:
                    n = n.left
                else:
                    n = n.right

            if (data < p.data):
              p.left = Node(data)
            else:
              p.right = Node(data)

    def inorder(self):
        self._inorder(self.root)
    def _inorder(self,node):
        if node is not None:
            self._inorder(node.left)
            print(" " + str(node.data), end="")
            self._inorder(node.right)
    def preorder(self):
        self._preorder(self.root)
    def _preorder(self,node):
        if node is not None:
            print(" " + str(node.data), end="")
            self._preorder(node.left)
            self._preorder(node.right)

n = int(input())
t = BST()
for i in range(0, n):
  line = input().split()

  if line[0] == "insert":
    t.insert(int(line[1]))
  elif line[0] == "print":
    t.inorder()
    print()
    t.preorder()
    print()

Submission status: Accepted

Solution code:
class BST:
  def __init__(self):
    self.root = None
  
  def insert(self, data):
    z = Node(data)
    y = None
    x = self.root

    while x:
      y = x
      if z.data < x.data:
        x = x.left
      else:
        x = x.right
    z.parent = y
    if y == None:
      self.root = z
    elif z.data < y.data:
      y.left = z
    else:
      y.right = z

  def print(self):
    print('',' '.join(map(str, self.root.inorder())))
    print('',' '.join(map(str, self.root.preorder())))


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

  def inorder(self):
    in_list = []
    if self.left:
      in_list += self.left.inorder()
    in_list += [self.data]
    if self.right:
      in_list += self.right.inorder()
    return in_list
  
  def preorder(self):
    pre_list = []
    pre_list += [self.data]
    if self.left:
      pre_list += self.left.preorder()
    #pre_list += [self.data]
    if self.right:
      pre_list += self.right.preorder()
    return pre_list

tree = BST()
n = int(input())
for _ in range(n):
  inp = input().split()
  if len(inp) == 2:
    tree.insert(int(inp[1]))
  else:
    tree.print()

Submission status: Accepted

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

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

    return T, root

def printPreorderList(p):
    if p == None:
        return
    print("",p.key,end = "")
    printPreorderList(p.left)
    printPreorderList(p.right)

def printInorderList(p):
    if p == None:
        return
    printInorderList(p.left)
    print("",p.key,end = "")
    printInorderList(p.right)
'''
def findRoot(T):
    if T == []:
        return None
    root = T[0].p
    while root != None:
        root = root.p
    return root
'''
n = int(input())
T=[]
root = None
for ni in range(n):
    s = input()
    if s[0] == "i":
        s, key = s.split()
        key = int(key)
        T, root = insert(T, Node(key), root)
    elif s[0] == "p":
        printInorderList(root)
        print()
        printPreorderList(root)
        print()

Submission status: Accepted

Solution code:
import sys


class Node(object):
    __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 walk(self, a, walk_type):
        if walk_type == 0:
            a.append(self.value)
        if self.left:
            self.left.walk(a, walk_type)
        if walk_type == 1:
            a.append(self.value)
        if self.right:
            self.right.walk(a, walk_type)
        if walk_type == 2:
            a.append(self.value)
        return a


class BinarySearchTree(object):
    __slots__ = ['root']
    
    def __init__(self):
        self.root: Node = None

    def insert(self, x: int):
        if self.root is 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 solve():
    tree = BinarySearchTree()
    input()
    for l in (l.split() for l in sys.stdin):
        if l[0] == "insert":
            tree.insert(int(l[1]))
        else:
            print('', *tree.root.walk([], 1))
            print('', *tree.root.walk([], 0))


if __name__ == "__main__":
    solve()

Submission status: Accepted

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

    def add_node(self, key):
        if key not in self.nodes:
            self.nodes[key] = Node(key)

    def insert(self, z_key):
        self.add_node(z_key)
        z = self.nodes[z_key]
        y = None  # xの親
        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 __str__(self):
        ans_in, ans_pre = [], []
        self.root.in_walk(ans_in)
        self.root.pre_walk(ans_pre)
        str_in = ' ' + ' '.join(map(str, ans_in))
        str_pre = ' ' + ' '.join(map(str, ans_pre))
        return str_in + '\n' + str_pre


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

    def pre_walk(self, ans):
        ans.append(self.key)
        if self.left:
            self.left.pre_walk(ans)
        if self.right:
            self.right.pre_walk(ans)

    def in_walk(self, ans):
        if self.left:
            self.left.in_walk(ans)
        ans.append(self.key)
        if self.right:
            self.right.in_walk(ans)


# ここからmain
tree = Tree()
n = int(input())
for i in range(n):
    line = list(map(str, input().split()))
    if line[0] == 'insert':
        key = int(line[1])
        tree.insert(key)
    else:
        print(tree)

Submission status: Accepted

Solution code:
class Node:
    def __init__(self, k):
        self.parent = None
        self.childs = [None, None]
        self.key = k


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

    def insert(self, z):
        y = None
        x = self.root
        while x != None:
            y = x
            if z.key < x.key:
                x = x.childs[0]
            else:
                x = x.childs[1]
        z.p = y
        if y == None:
            self.root = z
        elif z.key < y.key:
            y.childs[0] = z
        else:
            y.childs[1] = z


def preorder(p):
    s = ""
    if p == None:
        return ""
    s += f"{p.key} "
    s += preorder(p.childs[0])
    s += preorder(p.childs[1])
    return s


def inorder(p):
    s = ""
    if p == None:
        return ""
    s += inorder(p.childs[0])
    s += f"{p.key} "
    s += inorder(p.childs[1])
    return s


n = int(input())

t = Tree()
for i in range(n):
    v = input().split()
    if v[0] == "insert":
        t.insert(Node(int(v[1])))
    else:
        print(" "+inorder(t.root).strip())
        print(" "+preorder(t.root).strip())

Submission status: Accepted

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

class BinarySearchTree:
    def __init__(self):
        self.root = None
    
    def insert(self,key):
        node = Node(key, None)
        if self.root == None:
            self.root = node
        else:
            curr_node = self.root
            while curr_node:
                parent_node = curr_node
                if key <= curr_node.val:
                    curr_node = curr_node.left
                else:
                    curr_node = curr_node.right
            node.parent = parent_node
            if key <= parent_node.val:
                parent_node.left = node
            else:
                parent_node.right = node
        
    def preorderTraversal(self, node):
        result = []
        if node == None:
            return result
        result += [node.val]
        result += self.preorderTraversal(node.left)
        result += self.preorderTraversal(node.right)
        return result
        
    def inorderTraversal(self, node):
        result = []
        if node == None:
            return result
        result += self.inorderTraversal(node.left)
        result += [node.val]
        result += self.inorderTraversal(node.right)
        return result

N = int(input())
command = []
for i in range(N):
    command.append(tuple(input().split()))

T = BinarySearchTree()
for com in command:
    if com[0] == 'insert':
        T.insert(int(com[1]))
    if com[0] == 'print':
        In = T.inorderTraversal(T.root)
        Pre = T.preorderTraversal(T.root)
        print(' ' + ' '.join(list(map(str, In))))
        print(' ' + ' '.join(list(map(str, Pre))))

Submission status: Accepted

Solution code:
nodes = None


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


def insert(z):
    global nodes
    y = None
    x = nodes

    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:
        nodes = z
    elif z.key < y.key:
        y.left = z
    else:
        y.right = z


def get_inorder(inorder, node):
    if node.left is not None:
        get_inorder(inorder, node.left)
    inorder.append(node.key)
    if node.right is not None:
        get_inorder(inorder, node.right)
    return inorder


def get_preorder(preorder, node):
    preorder.append(node.key)
    if node.left is not None:
        get_preorder(preorder, node.left)
    if node.right is not None:
        get_preorder(preorder, node.right)
    return preorder


def p(node):
    print("", " ".join([str(i) for i in get_inorder([], node)]))
    print("", " ".join([str(i) for i in get_preorder([], node)]))


n = int(input())
for _ in range(n):
    s = input().split()
    if s[0] == "insert":
        key = int(s[1])
        insert(Node(key=key))
    else:
        p(nodes)

Submission status: Accepted

Solution code:
class Tree:
    def __init__(self):
        self.root = None
    
    def insert(self,x):
        z = Node(x)
        y = None
        x = self.root
        while x:
            y = x
            if z.data < x.data:
                x = x.left
            else:
                x = x.right
        z.parent = y
        if y == None:
            self.root = z
        elif z.data < y.data:
            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,data):
        self.data = data
        self.parent = None
        self.left = None
        self.right = None

    def prewalk(self):
        ret = [self.data]
        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.data]
        if self.right:
            ret += self.right.inwalk()
        return ret

    
tree = Tree()
n = int(input())
for _ in range(n):
    input_line = input()
    if input_line[0] == 'i':
        tree.insert(int(input_line.split()[1]))
    else:
        tree.print()