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:
class Node:
    def __init__(self, key):
        self.key = key
        self.parent = None
        self.left = self.right = None
    def preorder(self):
        L = [self.key]
        if self.left: L += self.left.preorder()
        if self.right: L += self.right.preorder()
        return L
    def inorder(self):
        L = []
        if self.left: L += self.left.inorder()
        L.append(self.key)
        if self.right: L += self.right.inorder()
        return L

def insert(t, z):
    y = None
    x = t
    while x:
        y = x # 親を設定
        x = x.left if z.key < x.key else x.right
    z.parent = y
    if not y: # t が空の場合
        return z
    if z.key < y.key:
        y.left = z # z を y の左の子にする
    else:
        y.right = z # z を y の右の子にする
    return t

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

t = None
m = int(input())
for _ in range(m):
    cmd = list(input().split())
    if cmd[0] == 'insert':
        t = insert(t, Node(int(cmd[1])))
    if cmd[0] == 'find':
        print('yes' if find(t, int(cmd[1])) else 'no')
    if cmd[0] == 'print':
        print('', *t.inorder())
        print('', *t.preorder())

Submission status: Accepted

Solution code:
n=int(input())
tree={}
root=None

def insert(tree,number):
    parent=None
    children=root
    while children!=None:
        parent=children
        if children>number:
            children=tree[parent][0]
        else:
            children=tree[parent][1]
    
    if parent>number:
        tree[parent][0]=number
    else:
        tree[parent][1]=number

def preorder(tree,i):
    if i==None:
        return
    print(" {}".format(str(i)),end="")
    preorder(tree,tree[i][0])
    preorder(tree,tree[i][1])

def inorder(tree,i):
    if i==None:
        return
    inorder(tree,tree[i][0])
    print(" {}".format(str(i)),end="")
    inorder(tree,tree[i][1])

def find(x,key):
    while x is not None and key!=x:
        if key<x:x=tree[x][0]
        else:x=tree[x][1]
    return x

for i in range(n):
    tmp=list(input().split())
    if tmp[0]=="print":
        inorder(tree,root)
        print()
        preorder(tree,root)
        print()
    else:
        number=int(tmp[1])
        if tmp[0]=="insert":
            if root is None:
                root=number
                tree[number]=[None,None]
            else:
                tree[number]=[None,None]
                insert(tree,number)
        else:
            if find(root,int(tmp[1])) is not None:print("yes")
            else:print("no")

Submission status: Accepted

Solution code:
import sys
# def input():
#     return sys.stdin.readline()[:-1]

# n = int(input())
# A = [input().split() for i in range(n)]

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


def insert(key):
    global root
    x = root # x is current node
    y = None  #  parent of x 
    while x:
        y = x # set parent
        if key < x.key:
            x = x.left # move to left child
        else:
            x = x.right #move to right child
    
    if root is None:
        root = Node(key)
    elif key < y.key: # set z as left child of y
        y.left = Node(key)
    else: 
        y.right = Node(key) # set z as right child of y
        
        
def find(key):
    x = root
    while x:
        if key==x.key:
            print('yes')
            return
        elif key < x.key:
            x = x.left
        else:
            x = x.right
    print('no')
    

def inorder(inorder_list, node):
    if node.left is not None:
        inorder(inorder_list, node.left)
    inorder_list.append(str(node.key))
    if node.right is not None:
        inorder(inorder_list, node.right)
    return inorder_list
        
def preorder(preorder_list, node):
    preorder_list.append(str(node.key))
    if node.left is not None:
        preorder(preorder_list, node.left)
    if node.right is not None:
        preorder(preorder_list, node.right)
    return preorder_list
        
root = None

input()
for o in sys.stdin:
    if o[0]=='i':
        insert(int(o[7:]))
    elif o[0]=='f':
        find(int(o[5:]))
    else:
        x = root
        inorder_list = inorder([], x)
        print(' '+' '.join(inorder_list))
        preorder_list = preorder([], x)
        print(' '+' '.join(preorder_list))

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


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


def insert(T, ROOT, z):
    if ROOT == z:
        T[z] = Node()
    else:
        T[z] = Node()  
        x = ROOT
        while x is not None:  
            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, ROOT, k):
    x = ROOT
    while x and k != x:
        if k < x:
            x = T[x].left
        else:
            x = T[x].right
    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 i == 0:
        ROOT = int(tmp[7:])
    if tmp[0] == "p":
        print_result(T)
    elif tmp[0] == "f":
        if find(T, ROOT, int(tmp[5:])):
            print("yes")
        else:
            print("no")
    else:
        insert(T, ROOT, int(tmp[7:]))

Submission status: Accepted

Solution code:
import sys, collections
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**10
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

class Node():
    key = None
    p = None
    left = None
    right = None

    def __init__(self, key):
        self.key = key

class BinarySearchTree():
    root = None

    def insert(self, 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.p = y

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

    def find(self, k):
        x = self.root
        while x is not None:
            if x.key==k:
                return True
            elif x.key>k:
                x = x.left
            else:
                x = x.right
        return False

    def print_nodes(self):
        inorder = []
        preorder = []

        def dfs(v):
            v_key = v.key
            preorder.append(v_key)
            if v.left is not None:
                dfs(v.left)
            inorder.append(v_key)
            if v.right is not None:
                dfs(v.right)

        dfs(self.root)

        print('', *inorder)
        print('', *preorder)

def resolve():
    m = I()
    T = BinarySearchTree()
    for _ in range(m):
        q = LSS()
        if q[0]=='insert':
            k = int(q[1])
            z = Node(k)
            T.insert(z)
        elif q[0]=='find':
            k = int(q[1])
            if T.find(k):
                print('yes')
            else:
                print('no')
        else:
            T.print_nodes()

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(2 ** 20)  # 再帰回数上限の向上 かなり多くしないとREになる


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


def insert(t: dict, i: int, r: int):
    if r > i:
        if t[r].left is not None:
            insert(t, i, t[r].left)
        else:
            t[r].left = i
    if r < i:
        if t[r].right is not None:
            insert(t, i, t[r].right)
        else:
            t[r].right = i


def inorder(t: dict, p: int, in_ls: list):
    if t[p].left is not None:
        inorder(t, t[p].left, in_ls)
    in_ls.append(p)
    if t[p].right is not None:
        inorder(t, t[p].right, in_ls)


def preorder(t: dict, p: int, pre_ls: list):
    pre_ls.append(p)
    if t[p].left is not None:
        preorder(t, t[p].left, pre_ls)
    if t[p].right is not None:
        preorder(t, t[p].right, pre_ls)


N = int(input())
T = {}
in_list = []
pre_list = []

order = list(map(str, input().split()))
root = int(order[1])
T[root] = Node(None, None)

for _ in range(N-1):
    order = str(input())
    if order[0] == 'i':
        order = list(order.split())
        T[int(order[1])] = Node(None, None)
        insert(T, int(order[1]), root)
    elif order[0] == 'f':
        order = list(order.split())
        if int(order[1]) in T:
            print('yes')
        else:
            print('no')
    else:
        inorder(T, root, in_list)
        print('', *in_list)
        preorder(T, root, pre_list)
        print('', *pre_list)
        in_list = []
        pre_list = []

Submission status: Accepted

Solution code:
class BinarySearchTree:
    def __init__(self):
        self.root = None
        self.nodes = []
        self.keys = set()

    def insert(self, z):
        self.keys.add(z)
        z = Node(z)
        self.nodes.append(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 dfs(self, node):
        self.preorder.append(node.key)
        if node.left is not None:
            self.dfs(node.left)

        self.inorder.append(node.key)

        if node.right is not None:
            self.dfs(node.right)

    def out(self):
        self.preorder = []
        self.inorder = []
        self.dfs(self.root)

        print("", *self.inorder)
        print("", *self.preorder)

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


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


def main():
    T = BinarySearchTree()
    n = int(input())
    for i in range(n):
        command = input().split()
        if command[0] == "print":
            T.out()
        elif command[0] == "find":
            T.find(int(command[1]))
        else:
            T.insert(int(command[1]))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
NIL = -1
class Node():
    def __init__(self, val):
        self.val = val
        self.parent = NIL
        self.left = NIL
        self.right = NIL
    def __str__(self):
        return "val:{}, parent:{}, left:{}, right:{}".format(self.val, self.parent, self.left, self.right)
        
class Tree():
    def __init__(self):
        self.Nodes = {}
        self.Nodes[NIL] = Node(NIL)
        self.root = self.Nodes[NIL]
        
    def insert(self, node):
        y = self.Nodes[NIL]
        x = self.root
        while x.val != NIL:
            y = x
            if(node.val < x.val):
                x = self.Nodes[x.left]
            else:
                x = self.Nodes[x.right]
        node.parent = y.val
        
        if(y.val == NIL):
            self.root = node
        elif(node.val < y.val):
            y.left = node.val
        else:
            y.right = node.val
        self.Nodes[node.val] = node
    
    def find(self, x):
        cur_n = self.root
        while (cur_n.val != NIL and cur_n.val != x):
#             print(x, cur_n)
            if(x < cur_n.val):
                cur_n = self.Nodes[cur_n.left]
            else:
                cur_n = self.Nodes[cur_n.right]
        return "yes" if cur_n.val != NIL else "no"

    def getPreOrder(self):
        return self.preParse(self.root.val, [])    
        
    def getInOrder(self):
        return self.inParse(self.root.val, [])
    
    def getPostOrder(self):
        return self.postParse(self.root.val, [])
        
    def inParse(self, u, res):
        if(u == NIL):
            return
        self.inParse(self.Nodes[u].left, res)
        res += [u]
        self.inParse(self.Nodes[u].right, res)
        return res

    def postParse(self, u, res):
        if(u == NIL):
            return
        self.postParse(self.Nodes[u].left, res)
        self.postParse(self.Nodes[u].right, res)
        res += [u]
        return res
    
    def preParse(self, u, res):
        if(u == NIL):
            return 
        res += [u]
        self.preParse(self.Nodes[u].left, res)
        self.preParse(self.Nodes[u].right, res)
        return res
        
n = int(input())

tree = Tree()
for row in range(n):
    operate = input().split()
    if(operate[0] == "insert"):
        tree.insert(Node(int(operate[1])))
        
    if(operate[0] == "print"):
        print(" {}".format( " ".join([str(ss) for ss in tree.getInOrder()])))
        print(" {}".format( " ".join([str(ss) for ss in tree.getPreOrder()])))
        
    if(operate[0] == "find"):
        print(tree.find(int(operate[1])))

Submission status: Accepted

Solution code:
from collections import deque
import sys
readline = sys.stdin.readline
write = sys.stdout.write

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 = root #Tの根
    y = None #親を設定
    while x is not None:
        y = x
        if key < x.key:
            x = x.left #左の子へ移動
        else:
            x = x.right  #右の子へ移動

    if y is None: #Tが空の場合
        root = Node(key)
    elif key < y.key:
        y.left = Node(key) #keyをyの左の子にする
    else:
        y.right = Node(key) #keyをyの右の子にする

# def find(key):
#     x = root
#     while x and key != x.key:
#         x = x.left if key < x.key else x.right
#     return x is None

def find(target):
    result = root
    while result and target != result.key:
        result = result.left if target < result.key else result.right
    return result is None # result が None ⇒ false

def inorder(node):
    return   inorder(node.left) + " "+ str(node.key) + inorder(node.right) if node else ''
def preorder(node):
    return   " " + str(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:]))
    elif e[0] == 'f':
        if find(int(e[5:])):
            print("no")
        else:
            print("yes")
        # print(['yes','no'][find(int(e[5:]))])
    else:
        print(inorder(root))
        print(preorder(root))

Submission status: Accepted

Solution code:
INFTY=2000000000+1

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

root=-1
T=[]
commands=[]
preorderList=[]
inorderList=[]

def readinput():
    global commands

    n=int(input())
    for _ in range(n):
        s=input().split()
        command=s[0]
        if(len(s)>1):
            op=s[1]
        commands.append((command,int(op)))

def insert(op):
    global T
    global root

    #print('[{}]'.format(op))
    zidx=len(T)
    z=Node(op)
    T.append(z)

    yidx=-1
    xidx=root
    while(xidx != -1):
        x=T[xidx]
        yidx=xidx
        if(z.key<x.key):
            xidx=x.left
            #print('left: {} < {}'.format(z.key, x.key))
        else:
            xidx=x.right
            #print('right')
    z.parent=yidx

    if yidx==-1:
        root=zidx
        #print('root changed')
    elif z.key<T[yidx].key:
        T[yidx].left=zidx
    else:
        T[yidx].right=zidx

def bisearch(p,op):
    '''再帰を使わないバージョン
    '''
    global T

    x=p
    while(x != -1 and T[x].key != op):
        if (op < T[x].key):
            x=T[x].left
        else:
            x=T[x].right

    if x==-1:
        return False
    else:
        return True


def find(op):
    ans=bisearch(root,op)
    if(ans==True):
        print('yes')
    else:
        print('no')


def getPreorderList(id):
    global preorderList

    preorderList.append(id)
    node=T[id]
    if(node.left!=-1):
        getPreorderList(node.left)
    if(node.right!=-1):
        getPreorderList(node.right)

def getInorderList(id):
    global inorderList

    node=T[id]
    if(node.left!=-1):
        getInorderList(node.left)
    inorderList.append(id)
    if(node.right!=-1):
        getInorderList(node.right)

def printPreorderList():
    for i in preorderList:
        print(' '+str(T[i].key),end='')
    print('')

def printInorderList():
    for i in inorderList:
        print(' '+str(T[i].key),end='')
    print('')

def printT():
    global inorderList
    global preorderList

    inorderList=[]
    preorderList=[]
    
    getInorderList(root)
    printInorderList()
    getPreorderList(root)
    printPreorderList()
    #for node in T:
    #    print(node.key, node.parent, node.left, node.right)    

def main():
    global commands

    for command,op in commands:
        if(command=='insert'):
            insert(op)
        elif(command=='find'):
            find(op)
        elif(command=='print'):
            printT()

if __name__=='__main__':
    readinput()
    main()

Submission status: Accepted

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

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

    def insert(self, data):
        n = self.root
        if n == None:
            self.root = Node(data)
            return
        else:
            while True:
                entry = n.key_value
                if data < entry:
                    if n.left is None:
                        n.left = Node(data)
                        return
                    n = n.left
                elif data > entry:
                    if n.right is None:
                        n.right = Node(data)
                        return
                    n = n.right
                else:
                    n.data = data
                    return

    def find(self,data):
        n = self.root
        if n == None:
            return False
        else:
            lst = []
            lst.append(n)
            while len(lst) > 0:
                node = lst.pop()
                if node.key_value == data:
                    return True
                if node.left != None and data < node.key_value:
                    lst.append(node.left)
                if node.right != None and data > node.key_value:
                    lst.append(node.right)
        return False

    def inorder(self,node):
        if node is None:
            return
        else:
            self.inorder(node.left)
            print(' {}'.format(node.key_value),end='')
            self.inorder(node.right)

    def preorder(self,node):
        if node is None:
            return
        else:
            print(' {}'.format(node.key_value),end='')
            self.preorder(node.left)
            self.preorder(node.right)

if __name__ == "__main__":
    n = int(input())

    bst = BST()
    for i in range(n):
        o = input().split()

        if o[0] == 'insert':
            bst.insert(int(o[1]))
        elif o[0] == 'print':
            bst.inorder(bst.root)
            print()
            bst.preorder(bst.root)
            print()
        elif o[0] == 'find':
            if bst.find(int(o[1])):
                print('yes')
            else:
                print('no')

Submission status: Accepted

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

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

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

def Preorder(target:Node):
    yield target.key
    if target.left != None:
        yield from Preorder(target.left)
    if target.right != None:
        yield from Preorder(target.right)

def Inorder(target:Node):
    if target.left != None:
        yield from Inorder(target.left)
    yield target.key
    if target.right != None:
        yield from Inorder(target.right)

def find(target:Node,findkey:int):
    if target.key == findkey:
        return True
    elif target.key > findkey:
        if target.left:
            return find(target.left, findkey)
    else:
        if target.right:
            return find(target.right, findkey)
    return False

from sys import stdin
tree = Tree()
n = int(input())
lines = stdin.readlines()
for line in lines:
    proc,*key = line.split()
    if proc == "insert":
        tree.insert(Node(int(key[0])))
    elif proc == "find":
        print("yes" if find(tree.root, int(key[0])) else "no")
    else:
        print(" ",end="")
        print(*Inorder(tree.root))
        print(" ",end="")
        print(*Preorder(tree.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, None

def insert(z):
    global root
    x, y = root, None
    while x:
        y = x
        if z < x.key:
            x = x.left
        else:
            x = x.right
    
    if y == None:
        root = Node(z)
    elif z < y.key:
        y.left = Node(z)
    else:
        y.right = Node(z)
        
def find(z):
    global root
    x, y = root, None
    while x:
        y = x
        if z < x.key:
            x = x.left
        elif z > x.key:
            x = x.right
        else:
            print("yes")
            return
    print("no")
        
def preorder(x):
    return f" {x.key}" + preorder(x.left) + preorder(x.right) if x else ""

def inorder(x):
    return inorder(x.left) + f" {x.key}" + inorder(x.right) if x else ""
        
input()
root = None
for s in sys.stdin:
    if s[0] == "p":
        print(inorder(root))
        print(preorder(root))
    elif s[0] == "f":
        find(int(s[5:]))
    else:
        insert(int(s[7:]))

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:
        y = x
        if key < x.key:
            x = x.left
        else:
            x = x.right

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

def find(key):
    global root
    x = root
    while x:
        if key < x.key:
            x = x.left
        elif key == x.key:
            return "yes"
        else:
            x = x.right
    return "no"
            
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 ''

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

Submission status: Accepted

Solution code:
from sys import stdin
N=int(input())
nodes=[None]*N
class node_tree():
    def __init__(self,node):
        self.node=node
        self.left=None
        self.right=None
        self.brother=None
        self.up=None

def ino(u):

    if u.left is not None:
        ino(u.left)
    print("",u.node,end="")
    if u.right is not None:
        ino(u.right)
def pre(u):
    print("",u.node,end="")
    if u.left is not None:
        pre(u.left)
    if u.right is not None:
        pre(u.right)
def search(u,key):
    if u.node <=key.node:
        if u.right is not None:
            search(u.right,key)
        else:u.right=key
    else:
        if u.left is not None:
            search(u.left,key)
        else:u.left=key
def find(u,key):
    if u.node==key:
        print("yes",end="")
        return
    if u.node < key:
        if u.right is not None:
            find(u.right, key)
        else:
            print("no",end="")
            return
    else:
        if u.left is not None:
            find(u.left, key)
        else:
            print("no",end="")
            return
command_list=[]*N
for i in range(N):
    command_list.append((stdin.readline().strip().split()))
for i,command in enumerate(command_list):
    if len(command)!=1:
        if command[0]=="find":
            find(nodes[0],int(command[1]))
            print()
        else:
            key=int(command[1])
            if i==0:
                nodes[i]=node_tree(key)
            else:
                ins=node_tree(key)
                search(nodes[0],ins)
                nodes[i]=ins
    else:
        ino(nodes[0])
        print()
        pre(nodes[0])
        print()

Submission status: Accepted

Solution code:
n = int(input())
inst_k = [-1]*n
inst = [-1]*n
for i in range(n):
    tmp = input().split()
    inst[i] = tmp[0]
    if len(tmp) == 2:
        inst_k[i] = int(tmp[1])

class BST:
    def __init__(self):
        self.key = []
        self.parent = []
        self.left_child = []
        self.right_child = []
        self.root = -1

    def insert(self,new_key):
        new_node = len(self.key)
        self.key.append(new_key)
        self.left_child.append(-1)
        self.right_child.append(-1)
        self.parent.append(-1)

        searching_node = self.root
        searching_node_parent = -1
        while searching_node != -1:
            searching_node_parent = searching_node
            if new_key < self.key[searching_node]:
                searching_node = self.left_child[searching_node]
            else:
                searching_node = self.right_child[searching_node]
        if searching_node_parent == -1:
            self.root = new_node
        else:
            self.parent[new_node] = searching_node_parent
            if new_key < self.key[searching_node_parent]:
                self.left_child[searching_node_parent] = new_node
            else:
                self.right_child[searching_node_parent] = new_node
    
    def print_clear(self):
        self.preorder_ans = []
        self.inorder_ans = []
    
    def preorder(self,node):
        if node != -1:
            self.preorder_ans.append(self.key[node])
            self.preorder(self.left_child[node])
            self.preorder(self.right_child[node])
    
    def inorder(self,node):
        if node != -1:
            self.inorder(self.left_child[node])
            self.inorder_ans.append(self.key[node])
            self.inorder(self.right_child[node])
    
    def find(self,key,node):
        if node == -1:
            return None
        else:
            if self.key[node] == key:
                return node
            else:
                if key < self.key[node]:
                    return self.find(key,self.left_child[node])
                else:
                    return self.find(key,self.right_child[node])
     
    def delete(self,key):
        del_node = self.find(key,self.root)
        if self.left_child[del_node] == -1 or self.right_child[del_node] == -1:
            instead_node = del_node
        else:
            instead_node = self.setSuccessor(del_node)

    def getSuccessor(self,node):
        if self.right_child[node] != -1:
            return getMinimum(self.right_child[node])
        else:
            ret = node
            while self.left_child[self.parent[ret]] != ret and ret != -1:
                ret = self.parent[ret]
    
    def getMinimum(self,node):
        while self.left_child[node] != -1:
            node = self.left_child[node]
        return node
        
        

            



tree = BST()
for i in range(n):
    if inst[i] == "insert":
        tree.insert(inst_k[i])
    elif inst[i] == "find":
        if tree.find(inst_k[i],tree.root) != None:
            print("yes")
        else:
            print("no")
    elif inst[i] == "print":
        tree.print_clear()
        tree.preorder(tree.root)
        tree.inorder(tree.root)
        print(" ",end = "")
        print(*tree.inorder_ans)
        print(" ",end = "")
        print(*tree.preorder_ans)