Problem:

Binary Search Tree II

Write a program which performs the following operations to a binary search tree $T$ by adding the find operation to A: Binary Search Tree I.

  
insert  $k$: Insert a node containing $k$ as key into $T$.

  
find $k$: Report whether $T$ has a node containing $k$. 

  
print: Print the keys of the binary search tree by inorder tree walk and  preorder tree walk respectively.

Input

  In the first line, the number of operations $m$ is given. In the following $m$ lines, operations represented by insert $k$, find $k$ or print are given.

Output

For each find $k$ operation, print "yes" if $T$ has a node containing $k$, "no" if not.

  In addition, 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

10
insert 30
insert 88
insert 12
insert 1
insert 20
find 12
insert 17
insert 25
find 16
print

Sample Output 1

yes
no
 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:
10
insert 30
insert 88
insert 12
insert 1
insert 20
find 12
insert 17
insert 25
find 16
print


Sample output:
yes
no
 1 12 17 20 25 30 88
 30 12 1 20 17 25 88

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2**20)

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

def pre_parse(T: dict, u: int, pre_ls: list):
    if u is 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: dict, u: int, in_ls: list):
    if u is 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: dict, ROOT: int , z: int):
    if ROOT == z:
        T[z] = Node()
    else:
        T[z] = Node()
        x = ROOT
        while x is not None: #子ノードがNoneになったらbreak
            next_parent = x
            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 find(T: dict, ROOT: int, k: int):
    """
    Tからkを見つけ出す。見つからなかったらNoneを返す
    """
    x = ROOT
    while x is not None and x != k:
        if k < x:
            x = T[x].left
        else:
            x = T[x].right
    return x

def delete_node(T: dict, z: int):
    # 1. zが子を持たない場合
    parent = T[z].parent
    if (T[z].left is None) and (T[z].right is None):
        # zを削除
        if T[parent].left == z:
            T[parent].left = None
        elif T[parent].right == z:
            T[parent].right = None
        else:
            raise ValueError
        del T[z]
    
    # 2. zがちょうど1つの子を持つ場合
    elif T[z].right is None:
        # 左だけ子がある場合
        is_z_left = True if T[parent].left == z else False
        child = T[z].left
        if is_z_left: # zが、zの親の左側の子なら
            T[parent].left = child
        else: # zが、zの親の右側の子なら
            T[parent].right = child
        T[child].parent = parent
        del T[z]
    
    elif T[z].left is None:
        # 右だけ子がある場合
        is_z_left = True if T[parent].left == z else False
        child = T[z].right
        if is_z_left: # zが、zの親の左側の子なら
            T[parent].left = child
        else: # zが、zの親の右側の子なら
            T[parent].right = child
        T[child].parent = parent
        del T[z]
    
    elif (T[z].left is not None) and (T[z].right is not None):
        left, right = T[z].left, T[z].right
        # 指定したノードの子孫の中で最も小さいノードを返す
        node_next_more = get_min_descendants(T, T[z].right)
        next_more_right = T[node_next_more].right
        next_more_parent = T[node_next_more].parent
        # z がROOTだったら
        if parent is None:
            if node_next_more == right:
                T[right].parent = None
                T[right].left = left
                ROOT = right
                del T[z]
                return
            else:
                # node_next_moreがもっと下にある場合
                T[node_next_more].left = left
                T[node_next_more].right = right
                T[node_next_more].parent = None
                T[left].parent = node_next_more # zの左側の子の親
                T[right].parent = node_next_more # zの右側の子の親
                # node_next_moreの親 -> node_next_more右子の接続
                T[next_more_parent].left = next_more_right
                if next_more_right is not None:
                    T[next_more_right].parent = next_more_parent
                
                del T[z]
                return
        
        else: # zが非ROOTだったら
            is_z_left = True if T[parent].left == z else False
            if node_next_more == right:
                # zをつぶしてzの(元)親の子の枠のうち、もともとｚがいた方に、zの右子を繋げる
                if is_z_left:
                    T[parent].left = right
                else:
                    T[parent].right = right
                T[right].parent = parent
                T[right].left = left
                del T[z]
                return
            else:
                # zの親->next_more
                if is_z_left:
                    T[parent].left = node_next_more
                else:
                    T[parent].right = node_next_more
                # next_more -> z の子
                T[node_next_more].left = left
                T[node_next_more].right = right
                T[node_next_more].parent = parent
                T[left].parent = node_next_more # ｚの左の接続
                T[right].parent = node_next_more # zの右の接続
                # node_next_moreの親 -> node_next_more右子の接続
                # (node_next_moreの親から見ると左に接続される)
                # next_moreはzの親と子の間に繋ぎ変えたので、
                # next_more_parentとnext_more_rightを繋げる。
                T[next_more_parent].left = next_more_right
                if next_more_right is not None:
                    # next_moreの右子があるなら、next_moreの分だけ詰める
                    T[next_more_right].parent = next_more_parent
                
                del T[z]
                return

def get_min_descendants(T:dict, z:int):
    x = z
    while T[x].left is not None:
        x = T[x].left
    return x

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

def main():
    N = int(input())
    T = {}
    ROOT = 0
    for i in range(N):
        tmp = input().split()
        if tmp[0] == "insert":
            value = int(tmp[1])
            if i==0:
                ROOT = value
            insert(T, ROOT, value)
        elif tmp[0] == "find":
            value = int(tmp[1])
            if find(T, ROOT, value):
                print("yes")
            else:
                print("no")
        elif tmp[0] == "delete":
            value = int(tmp[1])
            delete_node(T, value)
        else:
            print_result(T, ROOT)

main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2**20)#再帰回数上限の向上

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_lis: list):
    if u == None:
        return
    pre_lis.append(u)
    pre_parse(T, T[u].left, pre_lis)
    pre_parse(T, T[u].right, pre_lis)

def in_parse(T,u,in_lis):
    if u == None:
        return
    in_parse(T, T[u].left, in_lis)
    in_lis.append(u)
    in_parse(T, T[u].right, in_lis)

def insert(T, Root, z):
    #zは接点番号（そして接点番号が内容でもある）
    #この接点番号を二分探索木の条件に従うように挿入する
    #もしＴが空なら
    if Root == z:
        T[z] = Node()
    #もしTにいくつか入っていた場合
    else:
        T[z] = Node()#初期化
        x = Root
        while x is not None:
            #子供がNoneになったらbreakする。next_parentが挿入するものの親
            next_parent = x
            if x > z:
                x = T[x].left
                temp = 1
            else:
                x = T[x].right
                temp = 2

        T[z].parent = next_parent
        if temp == 1:
            T[next_parent].left = z
        else:
            T[next_parent].right = z

def find(T,Root,k):
    #Tからkを見つけ出す。ひたすらkの大きさによって左右のパスをたどっていくだけ。
    x = Root
    while x != None and x != k:
        if k < x:
            x = T[x].left
        else:
            x = T[x].right
    return x

def delete_node(T,z):
    # case1指定したzが子を持たないとき
    parent = T[z].parent
    if (T[z].left is None) and (T[z].right is None):
        #そのノードを消去する
        if T[parent].left == z:
            T[parent].left = None
        elif T[parent].right == z:
            T[parent].right = None
        else:
            raise ValueError("something wrong in case 1")

        del T[z]

    #case2 指定した子が一つの子を持つ場合
    elif T[z].right is None:
        #左の子だけある場合、左の子ノードを親に繋ぐ
        #親の左右どちらかにつけるかはzの繋がり方に依存する。
        z_is_left = True if T[parent].left == z else False
        child = T[z].left
        if z_is_left:
            T[parent].left = child
            T[child].parent = parent
            del T[z]
        else:
            T[parent].right = chile
            T[child].parent = parent
            del T[z]

    elif T[z].left is None:
        z_is_left = True if T[parent].left == z else False
        child = T[z].right
        if z_is_left:
            T[parent].left = child
        else:
            T[parent].right = child
        T[child].parent = parent
        del T[z]

    #case3 zが二つの子を持つ場合
    elif (T[z].left is not None) and (T[z].right is not None):
        left, right = T[z].left, T[z].right
        #指定したノードの右部分木の中の子孫の中で最も小さいノードをもらう
        node_next_more = get_min_in_descendants(T,T[z].right)
        next_more_right = T[node_next_more].right
        next_more_parent = T[node_next_more].parent
        #zがRootなら
        if parent is None:
            if node_next_more == right:
                #node_next_moreがrightの場合
                T[right].parent = None
                T[right].left = left
                Root = right
                del T[z]
                return

            else:
                #node_next_moreがもっと下流に存在する場合
                #zの子と親の接続
                T[node_next_more].left = left
                T[node_next_more].right = right
                T[node_next_more].parent = None
                T[left].parent = node_next_more
                T[right].parent = node_next_more
                if next_more_right is not None:
                    T[next_more_right].parent = next_more_parent
                    T[next_more_parent].left = next_more_right
                Root = node_next_more
                del T[z]
                return

        else:
            #zが非Root
            #zが親から見てどっち側についているか
            z_is_left = True if T[parent].left == z else False
            if node_next_more == right:
                if z_is_left:
                    T[parent].left = node_next_more
                else:
                    T[parent].right = node_next_more

                T[node_next_more].parent = parent
                T[node_next_more].left = left
                del T[z]
                return
            else:
                #zの親とnext_moreの接続
                if z_is_left:
                    T[parent].left = node_next_more
                else:
                    T[parent].right = node_next_more

                #next_moreと子供との接続
                T[node_next_more].left = T[z].left
                T[node_next_more].right = T[z].right
                T[node_next_more].parent = parent
                T[left].parent = node_next_more
                T[right].parent = node_next_more

                T[next_more_parent].left = next_more_right
                if T[next_more_right] is not None:
                    T[next_more_right].parent = next_more_parent

                del T[z]
                return

def get_min_in_descendants(T,z):
    x = z
    while T[x].left is not None:
        x = T[x].left

    return x

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)
    elif tmp.startswith('insert'):
        z = int(tmp.split()[1])
        if i == 0:
            Root = z
        insert(T,Root,z)
    elif tmp.startswith('find'):
        z = int(tmp.split()[1])
        if find(T,Root,z) is None:
            print('no')
        else:
            print('yes')
    elif tmp.startswith('delete'):
        z = int(tmp.split()[1])
        delete_node(T,z)

Submission status: Accepted

Solution code:
NIL = -1

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

def getAncestor(t, n):
    for i in range(n):
        if t[i].parent == -1:
            return i

def preOrderWolk(t, u, load=[]):
    load.append(u.key)
    if u.left != -1:
        load = preOrderWolk(t, u.left, load)
    if u.right != -1:
        load = preOrderWolk(t, u.right, load)
    return load

def preorder(u):
    if u == NIL:
        return
    print(' ' + str(u.key), end='')
    preorder(u.left)
    preorder(u.right)

def inorder(u):
    if u == NIL:
        return
    inorder(u.left)
    print(' ' + str(u.key), end='')
    inorder(u.right)

def inOrderTreeWalk(t, u, load=[]):
    if u.left != -1:
        load = inOrderTreeWalk(t, u.left, load)
    load.append(u.key)
    if u.right != -1:
        load = inOrderTreeWalk(t, u.right, load)
    return load

def find(x, k):
    """[finding Node which has key k]

    Args:
        x ([root Node]): [description]
        k ([int]): [description]
    """    
    while x != -1 and k != x.key:
        if k < x.key:
            x = x.left
        else:
            x = x.right
    return x


def insert(T, z):
    """[insert z to tree T]

    Args:
        T ([list]): [description]
        z ([Node class]): [Node ]
        r ([int]): [root intger]
    """
    y = NIL # x no parent
    x = T[0]
    while x != NIL and x.key != None:
        y = x
        if z.key < x.key:
            x = x.left
        elif z.key > x.key:
            x = x.right
    z.parent = y

    if y == NIL: ## T が空の場合
        T[0] = z
    elif z.key < y.key:
        T.append(z)
        y.left = z
    else:
        T.append(z)
        y.right = z


import sys
T = [Node(None)]
n = int(input())
r = 0
for _ in range(n):
    in_ = sys.stdin.readline().split()
    if in_[0][0] == 'i':
        z = Node(int(in_[1]))
        insert(T, z)
    elif in_[0][0] == 'f':
        key = int(in_[1])
        x = find(T[0], key)
        if x !=  -1:
            print('yes')
        else:
            print('no')
    else:
        inorder(T[0])
        print('')
        # pythonのprintは最後に改行記号をつけてくれるので、これで改行できる
        preorder(T[0])
        print('')

Submission status: Accepted

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

rt = None


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

def find(node, k):
    while node:
        if node.data == k:
            return True
        if k < node.data:
            node = node.left
        else:
            node = node.right
    return False

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

n = int(input())
b = [input() for i in range(n)]
for e in b:
    if e[0] == 'i': insert(int(e[7:]))
    elif e[0] =='f':
        if find(rt,int(e[5:])):
            print('yes')
        else:
            print('no')
    else:
        print(inorder(rt))
        print(preorder(rt))

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

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

class BST:
    def __init__(self):
        self.root=None
    def insert(self,key):
        node=Node(key)
        insert(self,node)


def insert(t,z):
    x=t.root
    y=None
    while x:
        y=x
        if z.key<x.key:
            x=x.left
        else:
            x=x.right
    z.parent=y
    
    if y==None:
        t.root=z
    elif z.key<y.key:
        y.left=z
    else:
        y.right=z

def preorder(x):
    print(" "+str(x.key),end="")
    if x.left != None:
        preorder(x.left)
    if x.right != None:
        preorder(x.right)
        
def inorder(x):
    if x.left != None:
        inorder(x.left)
    print(" "+str(x.key),end="")
    if x.right != None:
        inorder(x.right)

def find(t,k):
    while t:
        if t.key==k:
            return True
        if t.key > k:
            t=t.left
        else:
            t=t.right
    return False



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

Submission status: Accepted

Solution code:
class BinaryTree:
    class Node:
        def __init__(self, n):
            self.num = n
            self.parent = -1
            self.right = None
            self.left = None

    
    def __init__(self):
        self.root = None


    def insert(self, n):
        if not self.root:
            node = self.Node(n)
            self.root = node
        else:
            current, parent = self.root, None
            while current:
                parent = current
                if n < current.num:
                    current = current.left
                else:
                    current = current.right
            node = self.Node(n)
            node.parent = parent
            if n < parent.num:
                parent.left = node
            else:
                parent.right = node
                
            
    def find(self, n):
        if not self.root:
            return None
        current = self.root
        while current:
            if current.num == n:
                print('yes')
                return 
            elif n < current.num:
                current = current.left
            else:
                current = current.right
        print('no')

#    def load(self, tree_info):
#        for i in range(self.node_num):
#            self.nodes[i].num = tree_info[i][0]
#            self.nodes[i].left = tree_info[i][1]
#            self.nodes[i].right = tree_info[i][2]
#            if self.nodes[i].left != -1:
#                self.nodes[self.nodes[i].left].parent = self.nodes[i].num
#            if self.nodes[i].right != -1:
#                self.nodes[self.nodes[i].right].parent = self.nodes[i].num


    
    def print_preorder(self, node):
        if not node.left and not node.right:
            return [node.num]
        elif not node.left:
            return [node.num] + self.print_preorder(node.right)
        elif not node.right:
            return [node.num] + self.print_preorder(node.left)
        else:
            return [node.num] + self.print_preorder(node.left) + self.print_preorder(node.right)


    def print_inorder(self, node):
        if not node.left and not node.right:
            return [node.num]
        elif not node.left:
            return [node.num] + self.print_inorder(node.right)
        elif not node.right:
            return self.print_inorder(node.left) + [node.num]
        else:
            return self.print_inorder(node.left) + [node.num] + self.print_inorder(node.right)


    def print_postorder(self, node):
        if not node.left and not node.right:
            return [node.num]
        elif not node.left:
            return self.print_inorder(node.right) + [node.num]
        elif not node.right:
            return self.print_inorder(node.left) + [node.num]
        else:
            return self.print_inorder(node.left) + self.print_inorder(node.right) + [node.num]



if __name__ == '__main__':
    n = int(input())
    qs = [ input().rstrip().split() for _ in range(n) ]
    bt = BinaryTree()
    for q in qs:
        if q[0] == 'insert':
            bt.insert(int(q[1]))
        elif q[0] == 'find':
            bt.find(int(q[1]))
        elif q[0] == 'print':
            print(' ' + ' '.join(map(str,bt.print_inorder(bt.root))))
            print(' ' + ' '.join(map(str,bt.print_preorder(bt.root))))

Submission status: Accepted

Solution code:
import sys, os, math, bisect, itertools, collections, heapq, queue, copy, array

# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
# from decimal import Decimal
# from collections import defaultdict, deque

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


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


def insert(root, node):
    if root is None:
        root = node
    else:
        if root.val < node.val:
            if root.right is None:
                root.right = node
            else:
                insert(root.right, node)
        else:
            if root.left is None:
                root.left = node
            else:
                insert(root.left, node)


def preorder(root):
    ret = []
    if root is None: return ret
    ret.append(root.val)
    ret.extend(preorder(root.left))
    ret.extend(preorder(root.right))
    return ret


def inorder(root):
    ret = []
    if root is None: return ret
    ret.extend(inorder(root.left))
    ret.append(root.val)
    ret.extend(inorder(root.right))
    return ret


def find(node, key):
    while node is not None and key != node.val:
        if key < node.val:
            node = node.left
        else:
            node = node.right
    return node


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = ii()
    s, key = sl()
    root = BinaryNode(int(key))

    for n in range(N - 1):
        input = sl()
        if input[0] == 'print':
            print("", *inorder(root))
            print("", *preorder(root))
        elif input[0] == 'find':
            node = find(root, int(input[1]))
            print('yes' if node is not None else 'no')
        else:
            insert(root, BinaryNode(int(input[1])))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
###
# 二分探索木2
###

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

class BinarySearchTree:
    def __init__(self):
        self.root = None
        self.count = 0
    
    def insert(self, node: Node):
        self.count += 1
        if not self.root:
            self.root = node
            return

        cur = self.root
        while cur:
            if node.val > cur.val:
                if cur.right:
                    cur = cur.right
                    continue
                else:
                    cur.right,node.parent = node,cur
                    return
            else:
                if cur.left:
                    cur = cur.left
                    continue
                else:
                    cur.left,node.parent = node,cur
                    return

    def find(self, val):
        cur = self.root
        while cur:
            if cur.val == val:
                return "yes"
            elif cur.val > val:
                cur = cur.left
            else:
                cur = cur.right
        return "no"


def main():

    ## preorder tree walk
    preorder = []

    def preorder_walk(node):
        preorder.append(str(node.val))
        if node.left:
            preorder_walk(node.left)
        if node.right:
            preorder_walk(node.right)

    ## inorder tree walk

    inorder = []

    def inorder_walk(node):
        if node.left:
            inorder_walk(node.left)
        inorder.append(str(node.val))
        if node.right:
            inorder_walk(node.right)


    n = int(input())
    
    bst = BinarySearchTree()
    
    for _ in range(n):
        op = input().strip().split()
        if op[0] == "insert":
            bst.insert(Node(int(op[1])))
        elif op[0] == "print":
            preorder,inorder = [],[]
            preorder_walk(bst.root)
            inorder_walk(bst.root)
            print(""," ".join(inorder))
            print("", " ".join(preorder))
        elif op[0] == "find":
            print(bst.find(int(op[1])))

if __name__ == "__main__":
    main()

Submission status: Accepted

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

def insert(T, z):
    global root
    
    y = -1
    try:
        x = root
    except:
        x = -1
        root = z
        T[z].root = True
    
    while x != -1:
        y = x
        if T[z].key < T[x].key:
            x = T[x].left
        else:
            x = T[x].right
    T[z].parent = y
    
    if y == -1:
        pass
    
    elif T[z].key < T[y].key:
        T[y].left = z
        
    else:
        T[y].right = z

def find(T, z, s):
    if s == -1:
        return False
        
    elif T[s].key == z:
        return True
        
    elif T[s].key < z:
        return find(T, z, T[s].right)
        
    else:
        return find(T, z, T[s].left)
    
def preParse(u):
    if u == -1:
        return 0
    print(" " + str(T[u].key), end="")
    preParse(T[u].left)
    preParse(T[u].right)

def inParse(u):
    if u == -1:
        return 0
    inParse(T[u].left)
    print(" " + str(T[u].key), end="")
    inParse(T[u].right)

m = int(input().rstrip())

z = 0
T = []
for _ in range(m):
    T.append(BinaryTree(-1, -1, -1))

for _ in range(m):
    command = input().rstrip()
    if command =="print":
        inParse(root)
        print()
        preParse(root)
        print()
    else:
        command, key = command.split(" ")
        key = int(key)
    
    
    if command == "insert":
        T[z].key = key
        insert(T, z)
        z += 1
        
    elif command == "find":
        if find(T, key, root):
            print("yes")
        else:
            print("no")

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)

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

def insert(T:dict,z:int):
    global root
    y = -1
    x = root
    while x != -1:
        y = x
        if z < x:
            x = T[x].left
        else:
            x = T[x].right
    T[z] = Node(y,-1,-1)
    
    if y == -1:
        root= z
    elif z < y:
        T[y].left = z
    else:
        T[y].right = z

def find(T:dict,x:int,k:int):
    while x != -1 and k != x:
        if k < x:
            x = T[x].left
        else:
            x = T[x].right
    return x

def inorder(u:int):
    if u == -1:
        return 
    inorder(T[u].left)
    print(" "+str(u),end="")
    inorder(T[u].right)

def preorder(u:int):
    if u == -1:
        return 
    print(" "+str(u),end="")
    preorder(T[u].left)
    preorder(T[u].right)

n = int(input())
root = -1
T = {}
for _ in range(n):
    scan = input().split()
    if len(scan) == 1:
        inorder(root)
        print()
        preorder(root)
        print()
    else:
        k = int(scan[-1])
        if scan[0] == "insert":
            insert(T,k)
        else:
            print("yes" if find(T,root,k) != -1 else "no")

Submission status: Accepted

Solution code:
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 Tree:
    root = None
    preorder_list = []
    inorder_list = []
    def __init__(self):
        pass
    def insert(self, node):
        y = None
        x = self.root

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

        if y == None:
            self.root = node
        elif node.key < y.key:
            y.left = node
        else:
            y.right = node
    def find(self, node):
        y = None
        x = self.root
        while x is not None:
            if node.key == x.key:
                print('yes')
                return
            elif node.key < x.key:
                x = x.left
            else:
                x = x.right
        print('no')

    def display(self):
        #print(self.root, self.root.key, self.root.parent, self.root.left, self.root.right)
        self.inorder(self.root)
        self.preorder(self.root)
        print(' '+' '.join(map(str, self.inorder_list)))
        print(' '+' '.join(map(str, self.preorder_list)))
        pass

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

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

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

tree = Tree()
for command in command_list:
    if command[0] == 'insert':
        node = Node(int(command[1]))
        tree.insert(node)
        #print(node, node.key, node.parent, node.left, node.right)
    if command[0] == 'print':
        tree.display()
        tree.preorder_list = []
        tree.inorder_list = []
    if command[0] == 'find':
        tree.find(Node(int(command[1])))