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.

Solution (Python):
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:
            
            self.root = Node(val)
            return

        ptr = self.root 
        while True:
            if val < ptr.val:
                if ptr.left is None:
                    
                    ptr.left = Node(val)
                    ptr.left.parent = ptr
                    return
                ptr = ptr.left
            else:
                if ptr.right is None:
                    
                    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
        
        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=[]))

Solution (Python):



import sys
sys.setrecursionlimit(2**20)  


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


def pre_parse(T: dict, u: int, pre_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は接点番号(そしてその接点番号が内容でもある)
    この接点番号を二分探索木の条件に従うように挿入する。
    '''
    
    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):
    '''
    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'):  
        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')

Solution (Python):
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("")

Solution (Python):
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:]))

Solution (Python):

import sys


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)

Solution (Python):
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()

Solution (Python):
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()

Solution (Python):
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:]))

Solution (Python):
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])))

Solution (Python):
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)

Solution (Python):
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  
        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()

Solution (Python):

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()

Solution (Python):
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_tree_walk(nodes, root_node_no, inorder)
            print(" " + " ".join(map(str, inorder)))
            
            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()

Solution (Python):
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): 
    if (r.left != None):
        inorder(r.left)
    print(' ' + str(r.key), end ='')
    if (r.right != None):
        inorder(r.right)
def preorder(r):  
    print(" "+str(r.key), end ='')  
    if (r.left != None):  
        preorder(r.left) 
    if (r.right != None):
        preorder(r.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)