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
class Tree():
    def __init__(self):
        self.root = None
    def insert(self, key):
        z = Node(key)
        y = None
        x = self.root
        while x:
            y = x
            if z.key < x.key:
                x = x.left
            else:
                x = x.right
        z.parent = y
        if y == None:
            self.root = z
        elif z.key < y.key:
            y.left = z
        else:
            y.right = z
    def find(self, key):
        x = self.root
        while x and x.key != key:
            if x.key < key:
                x = x.right
            else:
                x = x.left
        print('yes' if x else 'no')
    def print(self):
        print('',' '.join(map(str, self.root.inwalk())))
        print('',' '.join(map(str, self.root.prewalk())))
    
class Node():
    def __init__(self, key):
        self.key = key
        self.parent = self.left = self.right = None
    def prewalk(self):
        ret = [self.key]
        if self.left:
            ret += self.left.prewalk()
        if self.right:
            ret += self.right.prewalk()
        return ret
    def inwalk(self):
        ret = []
        if self.left:
            ret += self.left.inwalk()
        ret += [self.key]
        if self.right:
            ret += self.right.inwalk()
        return ret
tree = Tree()
n = sys.stdin.readline()
for line in sys.stdin:
    if line[0] == 'i':
        tree.insert(int(line.split()[1]))
    elif line[0] == 'f':
        tree.find(int(line.split()[1]))
    else:
        tree.print()

Submission status: Accepted

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

class Node:
    __slots__ = ['value', 'parent', 'left', 'right']
    def __init__(self, value: int, parent: 'Node' = None):
        self.value = value
        self.parent = parent
        self.left: Node = None
        self.right: Node = None
    def inParse(self):
        if self.value == None:
            return
        if self.left != None:
            self.left.inParse()
        print(' {}'.format(self.value), end='')
        if self.right != None:
            self.right.inParse()
    def preParse(self):
        if self.value == None:
            return
        print(' {}'.format(self.value), end='')
        if self.left != None:
            self.left.preParse()
        if self.right != None:
            self.right.preParse()

class BinarySearchTree:
    __slots__ = ['root']
    def __init__(self):
        self.root: Node = None
    def insert(self, x: int):
        if self.root == None:
            self.root = Node(x)
            return
        parent, current = None, self.root
        while current:
            parent = current
            if x < current.value:
                current = current.left
            else:
                current = current.right
        if x < parent.value:
            parent.left = Node(x, parent)
        else:
            parent.right = Node(x, parent)
    def find(self, x: int):
        y = self.root
        while y != None and y.value != x:
            if y.value > x:
                y = y.left
            else:
                y = y.right
        return y

def main():
    tree = BinarySearchTree()
    n = int(input())
    for _ in range(n):
        inp = input()
        if inp[0] == 'i':
            com, num = inp.split()
            tree.insert(int(num))
        elif inp[0] == 'f':
            com, num = inp.split()
            if tree.find(int(num)):
                print('yes')
            else:
                print('no')
        else:
            tree.root.inParse()
            print()
            tree.root.preParse()
            print()

if __name__=='__main__': main()

Submission status: Accepted

Solution code:
import sys

m = int(input())

l, r = {}, {}

def insert(num):
    y = None
    x = root
    while True:
        y = x
        if num < x:
            try:
                x = l[x]
            except KeyError:
                break
        else:
            try:
                x = r[x]
            except KeyError:
                break
    if num < y:
        l[y] = num
    else:
        r[y] = num

def find(num):
    x = root
    while True:
        if num == x:
            print('yes')
            return
        elif num < x:
            try:
                x = l[x]
            except KeyError:
                print('no')
                return
        else:
            try:
                x = r[x]
            except KeyError:
                print('no')
                return

def inorder(num):
    try:
        inorder(l[num])
    except KeyError:
        pass
    print(' ' + str(num), end='')
    try:
        inorder(r[num])
    except KeyError:
        pass

def preorder(num):
    print(' ' + str(num), end='')
    try:
        preorder(l[num])
    except KeyError:
        pass
    try:
        preorder(r[num])
    except KeyError:
        pass

for i in range(m):
    order = sys.stdin.readline()
    if i == 0:
        global root
        root = int(order[7:])
        continue
    if order[0] == 'i':
        insert(int(order[7:]))
    elif order[0] == 'p':
        inorder(root)
        print()
        preorder(root)
        print()
    else:
        find(int(order[5:]))

Submission status: Accepted

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

n = int(input())
root = None
for index in range(n):
    inputL = input().split()
    if inputL[0] == 'insert':
        if root == None:
            root = binaryTreeNode(int(inputL[1]))
        else:
            def insertN(node, val, parent):
                if node != None:
                    if node.val > val:
                        insertN(node.left, val, node)
                    else:
                        insertN(node.right, val, node)
                else:
                    if parent.val > val:
                        parent.left = binaryTreeNode(val)
                    else:
                        parent.right = binaryTreeNode(val)
            insertN(root, int(inputL[1]), None)
    elif inputL[0] == 'print':
        inL = []
        def lookNodeIn(node):
            if node != None:
                lookNodeIn(node.left)
                inL.append(node.val)
                lookNodeIn(node.right)
        lookNodeIn(root)

        preL = []
        def lookNodePre(node):
            if node != None:
                preL.append(node.val)
                lookNodePre(node.left)
                lookNodePre(node.right)
        lookNodePre(root)

        print(' '+' '.join(list(map(str, inL))))
        print(' '+' '.join(list(map(str, preL))))
    
    else:
        def searchNode(node, val):
            if node != None:
                if node.val == val:
                    return 'yes'
                else:
                    if node.val > val:
                        return searchNode(node.left, val)
                    else:
                        return searchNode(node.right, val)
            return 'no'
        print(searchNode(root, int(inputL[1])))

Submission status: Accepted

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

def bst_insert(node, label):
    if node is None:
        return Node(label)

    elif label< node.label:
        node.left = bst_insert(node.left, label)
    else:
        node.right = bst_insert(node.right, label)
    return node

def bst_find(node, label):
    if node is None:
        return False
    elif label == node.label:
        return True
    elif label< node.label:
        return bst_find(node.left, label)
    elif label > node.label:
        return bst_find(node.right, label)




def bst_inorder(node):
    global In
    if (node.left is not None):
        bst_inorder(node.left)
    In.append(node.label)
    if (node.right is not None):
        bst_inorder(node.right)
    return

def bst_preorder(node):
    global Pre
    Pre.append(node.label)
    if (node.left is not None):
        bst_preorder(node.left)
    if (node.right is not None):
        bst_preorder(node.right)
    return

n= int(input())
tree = None
for i in range(n):
    cmmd = list(input().split( ))
    if cmmd[0] == "insert":
        k =int(cmmd[1])
        tree = bst_insert(tree, k)
    elif cmmd[0] == "find":
        k = int(cmmd[1])
        flag = bst_find(tree,k)
        if flag:
            print("yes")
        else:
            print("no")
        
    else:
        In =[]
        bst_inorder(tree)
        print("",*In)
        Pre =[]
        bst_preorder(tree)
        print("",*Pre)

Submission status: Accepted

Solution code:
class Node():
    def __init__(self, key, p, l, r):
        self.key, self.p, self.l, self.r = key, p, l, r


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

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

    def find(self, key, x=0):
        while x != -1 and key != self.tree[x].key:
            if key < self.tree[x].key:
                x = self.tree[x].l
            else:
                x = self.tree[x].r
        return x

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

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


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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

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


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

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

    return T


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

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

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


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

    ret.append(T.key)

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


def find(T, key):
    if key == T.key:
        return T

    elif key < T.key:
        if T.left is not None:
            ret = find(T.left, key)
            if ret is not None:
                return ret
    else:
        if T.right is not None:
            ret = find(T.right, key)
            if ret is not None:
                return ret

    return None


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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
class Node:
    parent = -1
    left = -1
    right = -1

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

    def __repr__(self):
        return "k:{},p:{},l:{},r:{}".format(self.key, self.parent, self.left, self.right)

root_node_no = -1

def insert(nodes :dict, in_node :Node):
    global root_node_no

    cur_node_no = root_node_no
    parent_node_no = -1
    while cur_node_no != -1:
        parent_node_no = cur_node_no
        if in_node.key < cur_node_no:
            cur_node_no = nodes[cur_node_no].left
        else:
            cur_node_no = nodes[cur_node_no].right

    in_node.parent = parent_node_no

    if root_node_no == -1:
        root_node_no = in_node.key
    elif in_node.key < parent_node_no:
        nodes[parent_node_no].left = in_node.key
    else:
        nodes[parent_node_no].right = in_node.key

    nodes[in_node.key] = in_node

def inorder_tree_walk(nodes, node_no ,inorder):
    if node_no == -1:
        return
    inorder_tree_walk(nodes, nodes[node_no].left, inorder)
    inorder.append(node_no)
    inorder_tree_walk(nodes, nodes[node_no].right, inorder)

def preorder_tree_walk(nodes, node_no, preorder):
    if node_no == -1:
        return
    preorder.append(node_no)
    preorder_tree_walk(nodes, nodes[node_no].left, preorder)
    preorder_tree_walk(nodes, nodes[node_no].right, preorder)


def find(nodes, tgt_node_no):
    cur_node_no = root_node_no
    while cur_node_no != -1:
        cur_node = nodes[cur_node_no]
        if cur_node.key == tgt_node_no:
            return True
        elif tgt_node_no < cur_node.key:
            cur_node_no = cur_node.left
        else:
            cur_node_no = cur_node.right

    return False


def main():
    num_com = int(input())
    commands = sys.stdin.readlines()
    nodes = {}
    for i in range(num_com):
        if commands[i][0] == 'i':
            insert(nodes, Node(int(commands[i][7:])))
        elif commands[i][0] == 'p':
            # inorder
            inorder = []
            inorder_tree_walk(nodes, root_node_no, inorder)
            print(" " + " ".join(map(str, inorder)))
            # preorder
            preorder = []
            preorder_tree_walk(nodes, root_node_no, preorder)
            print(" " + " ".join(map(str, preorder)))
        elif commands[i][0] == 'f':
            if find(nodes, int(commands[i][5:])):
                print('yes')
            else:
                print('no')


main()

Submission status: Accepted

Solution code:
class Node():
    def __init__(self,key):
        self.key = key
        self.parent = None
        self.left = None
        self.right = None
    def __str__(self):
        return str(self.key)
def inorder(r): ##r:root
    if (r.left != None):
        inorder(r.left)
    print(' ' + str(r.key), end ='')
    if (r.right != None):
        inorder(r.right)
def preorder(r):  ##r:root 
    print(" "+str(r.key), end ='')  ##preorder은 루트 쪽부터 print
    if (r.left != None):  ##left쪽으로 쭉감
        preorder(r.left) ##ns[i].left를 root로써 재귀함수!
    if (r.right != None):
        preorder(r.right) ##left다했으면 right으로도 똑같이 해줌 
root = None
def insert(z,root):
    y = None
    x = root
    while x != None:
        y = x
        if z.key < x.key:
            x = x.left
        else:
            x = x.right
    z.parent = y
    
    if z.key < y.key:
        y.left = z
    else:
        y.right = z

def find(z,root):
    flag = 0
    while root != None:
        k = root.key
        if k==z:
            flag = 1
            break
        elif z>k:
            root = root.right
        elif z<k:
            root = root.left
    if flag:
        print("yes")
    else:
        print("no")
        
    

n = int(input())
command = str(input())
if command[0]=="i":
    root = Node(int(command[7:]))
else:
    print()
for i in range(n-1):
    com = str(input())
    if com[0] == "i":
        insert(Node(int(com[7:])),root)
    elif com[0]=="p":
        inorder(root)
        print()
        preorder(root)
        print()
    elif com[0] == "f":
        find(int(com[5:]),root)

Submission status: Accepted

Solution code:
from typing import Optional


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


def print_preorder(node: Node) -> None:
    print(f" {node.key}", end="")
    if node.left is not None:
        print_preorder(node.left)
    if node.right is not None:
        print_preorder(node.right)


def print_inorder(node: Node) -> None:
    if node.left is not None:
        print_inorder(node.left)
    print(f" {node.key}", end="")
    if node.right is not None:
        print_inorder(node.right)


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

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

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

    assert root is not None
    return root


def find(root: Node, key: int) -> None:
    x: Optional[Node] = root

    while x is not None:
        if key == x.key:
            print("yes")
            return
        elif key < x.key:
            x = x.left
        else:
            x = x.right

    print("no")


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

Submission status: Accepted

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

parent_node = None

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

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

def find(u, num):
    while u != None and u.key != num:
        if num < u.key:
            u = u.left
        else:
            u = u.right
    if u != None:
        print("yes")
    else:
        print("no")

n = int(input())

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

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

        insert_node = Nodes[i]
        insert_node.key = key
        key_parent = None
        x = parent_node
            
        while x != None:
            key_parent = x
            if insert_node.key < x.key:
                x = x.left
            else:
                x = x.right
        insert_node.parent = key_parent
            
        if key_parent == None:
            parent_node = insert_node
        elif insert_node.key < key_parent.key:
            key_parent.left = insert_node
        else:
            key_parent.right = insert_node
    # プリント
    elif cmd[0] == 'print':
        printInorder(parent_node)
        print("")
        printPreorder(parent_node)
        print("")
    # サーチ
    else:
        key = int(cmd[1])
        find(parent_node, key)

Submission status: Accepted

Solution code:
root = None

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

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

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

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

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

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

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

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

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

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

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

n = int(input())

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

Submission status: Accepted

Solution code:
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 TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


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

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

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

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

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

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

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

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

    def find(self, target):
        if not self.root:
            return False
        r = self.root
        while r:
            if target < r.val:
                r = r.left
            elif target == r.val:
                return True
            else:
                r = r.right
        return False


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

Submission status: Accepted

Solution code:
NIL = -1


class Node():
    __slots__ = ["key", "parent", "left", "right"]

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


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

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

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

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

    def find(self, key):
        now = self.root
        while now != NIL:
            if   key < now.key:
                now = now.left
            elif key > now.key:
                now = now.right
            else:
                break

        return now

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

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

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

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



n = int(input())

root = Node()
binary_tree = BinaryTree(root)


for _ in range(n):

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

    if   command == "insert":
        k = int(list_num[0])
        binary_tree.insert(k)
    elif command == "find":
        k = int(list_num[0])
        if isinstance(binary_tree.find(k), int):
            print("no")
        else:
            print("yes")
    elif command == "print":
        binary_tree.treewalk_inorder(root)
        print()
        binary_tree.treewalk_preorder(root)
        print()
    else:
        raise

Submission status: Accepted

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

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

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

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

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

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

    z.parent = y

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

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

m = int(input())
root = None

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

    if arr[0] == 'find':
        k = int(arr[1])
        if find(root, k):
            print('yes')
        else:
            print('no')
        continue

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

    insert(root, Node(id))