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 BinarySearchTree:
    def __init__(self):
        self.lcs = {}
        self.rcs = {}
        self.root = None

    def insert(self, key):
        if self.root is None:
            self.root = key
            self.lcs[key] = None
            self.rcs[key] = None
            return
        parent = self.root
        while True:
            if key < parent:
                if self.lcs[parent] is None:
                    self.lcs[parent] = key
                    self.lcs[key] = None
                    self.rcs[key] = None
                    break
                else:
                    parent = self.lcs[parent]
            else:
                if self.rcs[parent] is None:
                    self.rcs[parent] = key
                    self.lcs[key] = None
                    self.rcs[key] = None
                    break
                else:
                    parent = self.rcs[parent]

    def _find(self, key, cur):
        if key == cur:
            return True
        elif key < cur:
            if self.lcs[cur] is None:
                return False
            else:
                return self._find(key, self.lcs[cur])
        else:
            if self.rcs[cur] is None:
                return False
            else:
                return self._find(key, self.rcs[cur])

    def find(self, key):
        return self._find(key, self.root)

    def _print(self, cur):
        self.preorder.append(cur)
        if self.lcs[cur]:
            self._print(self.lcs[cur])
        self.inorder.append(cur)
        if self.rcs[cur]:
            self._print(self.rcs[cur])

    def print(self):
        self.preorder = []
        self.inorder = []
        self._print(self.root)
        print(' ' + ' '.join(map(str, self.inorder)))
        print(' ' + ' '.join(map(str, self.preorder)))


T = BinarySearchTree()
N = int(input())
for _ in range(N):
    s = input().split()
    if s[0] == 'insert':
        T.insert(int(s[1]))
    elif s[0] == 'find':
        print('yes' if T.find(int(s[1])) else 'no')
    else:
        T.print()

Submission status: Accepted

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

class Tree:
    def __init__(self):
        self.root = None
        self.list = []
    
    def insert(self, node_tobe_added):
            y = None #「xの親」って書いてあるけど、「zの親」では？
            x = self.root
            while x != None:
                #ここで親を設定する。xを一つずつ葉に進めて、yに代入する。yがｚの親になる。
                y = x
                if node_tobe_added.key < x.key:
                    x = x.left
                else:
                    x = x.right
            #ここでyがzの親に設定される。
            node_tobe_added.parent = y 
            
            #yがNoneなら何もないということなのでzがrootになる。
            if y == None:
                self.root = node_tobe_added
            elif node_tobe_added.key < y.key:
                #node_tobe_addedをyの左の子にする
                y.left = node_tobe_added
            else:
                #node_tobe_addedをyの右の子にする
                y.right = node_tobe_added
                
    def find(self, key):
        x = self.root
        while x != None and key != x.key:
            if key < x.key:
                x = x.left
            else:
                x = x.right
        return x
                
    def preParse(self, node):
        if node == None:
            return
        self.list.append(node.key)
        self.preParse(node.left)
        self.preParse(node.right)
    
    def inParse(self, node):
        if node == None:
            return
        self.inParse(node.left)
        self.list.append(node.key)
        self.inParse(node.right)

T = Tree()

N = int(input())
for i in range(N):
        order, *key = input().split() #printの場合はkeyがないので、*をつけて配列として扱う。
        if order == "print":
            T.list = []
            T.inParse(T.root)
            print(" " + " ".join(map(str, T.list)))
            T.list = []
            T.preParse(T.root)
            print(" " + " ".join(map(str, T.list)))
        elif order == "insert":#insertの場合
            T.insert(Node(int(key[0]))) #なぜかわからないがintにしないとWAになる。
        else:
            if T.find(int(key[0])):
                print("yes")
            else:
                print("no")

Submission status: Accepted

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

class BinaryTree():
    def __init__(self):
        self.root = None
    
    def insert(self, value):
        if self.root == None:
            self.root = Node(value)
        else:
            parentnode = curnode = self.root
            while curnode != None:
                parentnode = curnode
                if curnode.value > value:
                    curnode = curnode.left
                else:
                    curnode = curnode.right
            if value > parentnode.value:
                parentnode.right = Node(value)
            else:
                parentnode.left = Node(value)

    def find(self, value):
        curnode = self.root
        while curnode != None:
            if curnode.value == value:
                return True
            elif curnode.value < value:
                curnode = curnode.right
            else:
                curnode = curnode.left
        return False

    def preorder(self, root):
        if root == None:
            pass
        else:
            print(' %d' % root.value, end='')
            self.preorder(root.left)
            self.preorder(root.right)

    def inorder(self, root):
        if root == None:
            pass
        else:
            self.inorder(root.left)
            print(' %d' % root.value, end='')
            self.inorder(root.right)

if __name__ == '__main__':
    n = int(input())
    binarytree = BinaryTree()
    for _ in range(n):
        common = input()
        if common[0] == 'i':
            binarytree.insert(int(common[7:]))
        elif common[0] == 'f':
            if binarytree.find(int(common[5:])):
                print('yes')
            else:
                print('no')
        else:
            binarytree.inorder(binarytree.root)
            print()
            binarytree.preorder(binarytree.root)
            print()

Submission status: Accepted

Solution code:

class Node:
    key = None
    parent = None
    left = None
    right = None

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


def insert(key):
    global T
    global root

    new_node = Node(key)
    T.append(new_node)

    if root is None:
        root = new_node

    else:
        y = None  # 親
        x = root  # 子

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

        new_node.parent = y
        if new_node.key < y.key:
            y.left = new_node
        else:
            y.right = new_node


def find(key):
    global T
    global root

    x = root

    while x is not None and key != x.key:
        # print(key, x.key)

        if key < x.key:
            x = x.left
        else:
            x = x.right
    return x  # マッチしなければNONEが戻る。


def in_order(node, order):
    if node is None:
        return

    in_order(node.left, order)
    order.append(node.key)
    in_order(node.right, order)


def pre_order(node, order):
    if node is None:
        return

    order.append(node.key)
    pre_order(node.left, order)
    pre_order(node.right, order)


m = int(input())
T = []
root = None

for i in range(m):
    order = input()

    if order.startswith('print'):
        output = []
        in_order(root, output)
        # print(output)
        print(' ' + ' '.join(map(str, output)))

        output = []
        pre_order(root, output)
        # print(output)
        print(' ' + ' '.join(map(str, output)))

    elif order.startswith('find'):
        order, value = order.split()
        value = int(value)
        _ = find(value)
        if _ is None:
            print('no')
        else:
            print('yes')

    else:
        order, value = order.split()
        value = int(value)
        insert(value)

Submission status: Accepted

Solution code:
class Node:
    def __init__(self, v=None, l=None, r=None):
        self.value = v
        self.left = l
        self.right = r

class Tree:
    def __init__(self):
        self.root = Node()
    
    def insert(self, v):
        if self.root.value is None:
            self.root.value = v
            return
        node = self.root
        while node is not None:
            if v < node.value:
                if node.left is None:
                    node.left = Node(v)
                    return
                node = node.left
            else:
                if node.right is None:
                    node.right = Node(v)
                    return
                node = node.right

    def find(self, v):
        node = self.root
        while node != None:
            if v == node.value:
                print "yes"
                return
            elif v < node.value:
                node = node.left
            else:
                node = node.right
        print "no"
        return

    def print_tree(self, order):
        ans = []
        def rec(node):
            if node is None:
                return
            if order == "pre":
                ans.append(str(node.value))
            if node.left is not None:
                rec(node.left)
            if order == "in":
                ans.append(str(node.value))
            if node.right is not None:
                rec(node.right)
        rec(self.root)
        print " " + " ".join(ans)

tree = Tree()
N = int(raw_input())
for _ in range(N):
    d = raw_input().split()
    cmd = d[0]
    if cmd == "insert":
        tree.insert(int(d[1]))
    elif cmd == "find":
        tree.find(int(d[1]))
    elif cmd == "print":
        tree.print_tree("in")
        tree.print_tree("pre")

Submission status: Accepted

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

root = None
def insert(z):
    global root
    y = None
    x = root
    while x is not None:
        y = x
        if z[2] < x[2]:
            x = x[0]
        else:
            x = x[1]
    z[3] = y

    if y is None:
        root = z
    elif z[2] < y[2]:
        y[0] = z
    else:
        y[1] = z

def find(k):
    x = root
    while x is not None:
        if x[2] == k:
            return 1
        if k < x[2]:
            x = x[0]
        else:
            x = x[1]
    return 0

def debug():
    s0 = [""]
    s1 = [""]

    def dfs(nd):
        v = str(nd[2])
        s0.append(v)
        if nd[0] is not None:
            dfs(nd[0])
        s1.append(v)
        if nd[1] is not None:
            dfs(nd[1])
    dfs(root)
    return " ".join(s1), " ".join(s0)


M = int(readline())
ans = []
for m in range(M):
    cmd, *V, = readline().split()
    if cmd == "print":
        ans.extend(debug())
    elif cmd == "find":
        ans.append("yes" if find(int(V[0])) else "no")
    else:
        insert([None, None, int(V[0]), None])
write("\n".join(ans))
write("\n")

Submission status: Accepted

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

def insert(z):
    global root
    if root==None:
        root=Node(z)
    else:
        x=root
        while True:
            if z<x.key:
                if x.left:
                    x=x.left
                else:
                    x.left=Node(z)
                    break
            else:
                if x.right:
                    x=x.right
                else:
                    x.right=Node(z)
                    break
def inorder(z):
    if z==None:
        return []
    else:
        return inorder(z.left)+[z.key]+inorder(z.right)
def preorder(z):
    if z==None:
        return []
    else:
        return [z.key]+preorder(z.left)+preorder(z.right)
def find(z):
    global root
    x=root
    r="no"
    while x:
        if z==x.key:
            r="yes"
            break
        elif z<x.key:
            x=x.left
        else:
            x=x.right
    return r
root=None
n=int(input())
for _ in range(n):
    p=input()
    if p[0]=="i":
        insert(int(p[7:]))
    elif p[0]=="f":
        print(find(int(p[5:])))
    else:
        print("",*inorder(root))
        print("",*preorder(root))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
btree = []
root = None


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


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


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


def insert(key):
    global root
    z = Node(key, None, None, None)
    y = None
    x = root
    while x is not None:
        y = x
        if z.key < x.key:
            x = x.left  # 左の子へ移動
        else:
            x = x.right  # 右の子へ移動

    z.parent = y

    if y is None:
        root = z
    elif z.key < y.key:
        y.left = z  # zをyの左の子にする
    else:
        y.right = z  # zをyの右の子にする


def find(key):
    global root
    x = root
    while x is not None:
        if x.key == key:
            print('yes')
            return
        elif x.key > key:
            x = x.left
        else:
            x = x.right
    print('no')



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


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

        operation = input().split()

        # print(operation)

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

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

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

def find(T, k):
    u = root
    while u != -1 and k != u:
        if k < u:
            u = T[u].l
        else:
            u = T[u].r
    return "no" if u == -1 else "yes"

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

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

Submission status: Accepted

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


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

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

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

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

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

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

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

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

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

Submission status: Accepted

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


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


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


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


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


def find(T, ROOT, k):
    '''
    Tからkを見つけ出す。見つからなかったらNoneを返す
    ひたすらkの大きさによって左右のパスをたどっていくだけ
    (いま辞書でノードを管理しているので、`k in T.keys()`で済むことではあるんだけど(オーダーは大きくなる)))
    '''
    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 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'):  # なぜかtmp == 'print'ではerror
        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')

Submission status: Accepted

Solution code:
from typing import List, Optional


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


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


def insert(T: Tree, z: Node) -> None:
	y: Optional[Node] = None
	x: Optional[Node] = T.root
	while x is not None:
		y = x # 親を設定
		if z.key < x.key:
			x = x.left
		else:
			x = x.right
	z.parent = y

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


def find(k: int) -> str:
	z = T.root
	while z is not None:
		if k == z.key:
			return "yes"
		elif k < z.key:
			z = z.left
		else:
			z = z.right
	return "no"


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


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


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

Submission status: Accepted

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

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

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

def Find(root, key):
    if root.node == key:
        print("yes")
    elif root.left == None and key < root.node:
        print("no")
    elif root.right == None and root.node < key:
        print("no")
    else:
        if key < root.node:
            Find(root.left, key)
        else:
            Find(root.right, key)
        

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

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

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

Submission status: Accepted

Solution code:
# ALDS1_8_B Binary Search Tree II
import sys

# ALDS1_8_A Binary Search Tree 1
import sys


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


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

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

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

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

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

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

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

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

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

    def find(self, num, node):
        if num < node.key:
            if node.left:
                self.find(num, node.left)
            else:
                print('no')
        elif num > node.key:
            if node.right:
                self.find(num, node.right)
            else:
                print('no')
        else:
            print('yes')
            return


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

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