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 BST:
  def __init__(self):
    self.root = None
  
  def insert(self, data):
    z = Node(data)
    y = None
    x = self.root

    while x:
      y = x
      if z.data < x.data:
        x = x.left
      else:
        x = x.right
    z.parent = y
    if y == None:
      self.root = z
    elif z.data < y.data:
      y.left = z
    else:
      y.right = z

  def find(self, data):
    x = self.root
    z = Node(data)
    while x and data != x.data:
      if z.data < x.data:
        x = x.left
      else:
        x = x.right
    if x is not None:
      return True
    else:
      return False


  def print(self):
    print('',' '.join(map(str, self.root.inorder())))
    print('',' '.join(map(str, self.root.preorder())))


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

  def inorder(self):
    in_list = []
    if self.left:
      in_list += self.left.inorder()
    in_list += [self.data]
    if self.right:
      in_list += self.right.inorder()
    return in_list
  
  def preorder(self):
    pre_list = []
    pre_list += [self.data]
    if self.left:
      pre_list += self.left.preorder()
    #pre_list += [self.data]
    if self.right:
      pre_list += self.right.preorder()
    return pre_list

tree = BST()
n = int(input())
for _ in range(n):
  inp = input().split()
  if len(inp) == 2:
    if inp[0] == "insert":
      tree.insert(int(inp[1]))
    else:
      x = tree.find(int(inp[1]))
      if tree.find(int(inp[1])):
        print("yes")
      else:
        print("no")
  else:
    tree.print()

Submission status: Accepted

Solution code:
class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
        self.p = 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.p = y
    if y == None:
        root = z
    elif z.key < y.key:
        y.left = z
    else:
        y.right = z

    return root

def printPreorderList(p):
    if p == None:
        return
    print("",p.key,end = "")
    printPreorderList(p.left)
    printPreorderList(p.right)

def printInorderList(p):
    if p == None:
        return
    printInorderList(p.left)
    print("",p.key,end = "")
    printInorderList(p.right)

def find(key, root):
    x = root
    while x != None:
        if key == x.key:
            print("yes")
            return
        elif key < x.key:
            x = x.left
        else:
            x = x.right
    print("no")


n = int(input())
root = None
for ni in range(n):
    s = input()
    if s[0] == "i":
        s, key = s.split()
        key = int(key)
        root = insert(Node(key), root)
    elif s[0] == "p":
        printInorderList(root)
        print()
        printPreorderList(root)
        print()
    elif s[0] == "f":
        s, key = s.split()
        key = int(key)
        find(key, root)

Submission status: Accepted

Solution code:
class BinarySearchTree(object):
    __slots__ = ['root']

    def __init__(self):
        self.root = None

    def insert(self, key):
        new_node = [key, None, None]

        if self.root is None:
            self.root = new_node
            return

        parent, child = None, self.root
        while child:
            parent = child
            child = child[1] if key < child[0] else child[2]

        if key < parent[0]:
            parent[1] = new_node
        else:
            parent[2] = new_node

    def find(self, key):
        current = self.root
        while current and current[0] != key:
            current = current[1] if key < current[0] else current[2]

        return current

    def walk(self, walk_type):
        a = []
        self._walk(self.root, a, walk_type)
        return a

    def _walk(self, node, a, walk_type):
        if walk_type == 0:
            a.append(node[0])
        if node[1]:
            self._walk(node[1], a, walk_type)
        if walk_type == 1:
            a.append(node[0])
        if node[2]:
            self._walk(node[2], a, walk_type)


if __name__ == '__main__':
    import sys
    input()
    tree = BinarySearchTree()

    for cmd in (l.split() for l in sys.stdin):
        if cmd[0] == 'insert':
            tree.insert(int(cmd[1]))
        elif cmd[0] == 'find':
            print('yes' if tree.find(int(cmd[1])) else 'no')
        else:
            print('', *tree.walk(1))
            print('', *tree.walk(0))

Submission status: Accepted

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

    x = root
    y = None
    while x:x, y = x.left if key < x.key else x.right , x
    if y == None:root = Node(key)
    elif y.key < key:y.right = Node(key)
    else:y.left = Node(key)
        
        
def pre(node):
    if node == None:return
    print('',node.key, end = '');pre(node.left);pre(node.right)
    
def ino(node):
    if node == None:return
    ino(node.left);print('',node.key,end='');ino(node.right)

def find(node, key):
    if node == None:
        print('no');return
    if node.key == key:
        print('yes');return
    elif node.key > key:
        find(node.left, key)
    else:
        find(node.right, key)

def delete(node, key):
    x = node
    while x.key != key and x:
        x, y = node.left if key < x.key else x.right, x
    if x == None:
        return
    else:
        if x.left == None and x.right == None:
            if key < y.key:y.left = None
            else:y.right = None
        elif x.right == None:
            if key < y.key:y.left = x.left
            else:y.right = x.left
        elif x.left == None:
            if key > y.key:y.right = x.right
            else:y.left = x.right
        else:
            a = x.right
            c = 0
            b = 1
            while a:a, b, c = a.left if a.left != None and a.right != None else a.left if a.left != None else None  , a, b
            if c == 1:
                b.left = x.left
                if key < y.key:y.left = b
                else:y.right = b
            else:
                c.left = b.right
                x.key = b.key
                
                
            
        
        
    

n = int(input())
root = None
for j in range(n):
    s, *i = input().split()
    if s[0] == 'i':insert(int(i[0]))
    elif s[0] == 'f':
        find(root, int(i[0]))
    elif s[0] == 'd':
        delete(root, int(i[0]))
    else:
        ino(root);print();pre(root);print()

Submission status: Accepted

Solution code:
class Tree():
    def __init__(self):
        self.nodes = {}
        self.root = None

    def add_node(self, key):
        if key not in self.nodes:
            self.nodes[key] = Node(key)

    def insert(self, z_key):
        self.add_node(z_key)
        z = self.nodes[z_key]
        y = None  # xの親
        x = self.root
        while x is not None:
            y = x  # 親を設定
            if z.key < x.key:
                x = x.left
            else:
                x = x.right
        z.parent = y

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

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

    def __str__(self):
        ans_in, ans_pre = [], []
        self.root.in_walk(ans_in)
        self.root.pre_walk(ans_pre)
        str_in = ' ' + ' '.join(map(str, ans_in))
        str_pre = ' ' + ' '.join(map(str, ans_pre))
        return str_in + '\n' + str_pre


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

    def pre_walk(self, ans):
        ans.append(self.key)
        if self.left:
            self.left.pre_walk(ans)
        if self.right:
            self.right.pre_walk(ans)

    def in_walk(self, ans):
        if self.left:
            self.left.in_walk(ans)
        ans.append(self.key)
        if self.right:
            self.right.in_walk(ans)


# ここからmain
tree = Tree()
n = int(input())
for i in range(n):
    line = list(map(str, input().split()))
    if line[0] == 'insert':
        key = int(line[1])
        tree.insert(key)
    elif line[0] == 'find':
        key = int(line[1])
        tree.find(key)
    else:
        print(tree)

Submission status: Accepted

Solution code:
class Node:
    def __init__(self, k):
        self.parent = None
        self.childs = [None, None]
        self.key = k


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

    def insert(self, z):
        y = None
        x = self.root
        while x != None:
            y = x
            if z.key < x.key:
                x = x.childs[0]
            else:
                x = x.childs[1]
        z.p = y
        if y == None:
            self.root = z
        elif z.key < y.key:
            y.childs[0] = z
        else:
            y.childs[1] = z

    def find(self, k):
        x = self.root
        while x != None:
            if k == x.key:
                return True
            if k < x.key:
                x = x.childs[0]
            else:
                x = x.childs[1]
        return False


def preorder(p):
    s = ""
    if p == None:
        return ""
    s += f"{p.key} "
    s += preorder(p.childs[0])
    s += preorder(p.childs[1])
    return s


def inorder(p):
    s = ""
    if p == None:
        return ""
    s += inorder(p.childs[0])
    s += f"{p.key} "
    s += inorder(p.childs[1])
    return s


n = int(input())

t = Tree()
for i in range(n):
    v = input().split()
    if v[0] == "insert":
        t.insert(Node(int(v[1])))
    elif v[0] == "find":
        print("yes" if t.find(int(v[1])) else "no")
    else:
        print(" "+inorder(t.root).strip())
        print(" "+preorder(t.root).strip())

Submission status: Accepted

Solution code:
import sys

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

def insert(node,x):
    if node is None:
        node = Node(x)
    elif node.data == x:
        return node
    elif node.data > x:
        node.left = insert(node.left,x)
    else:
        node.right = insert(node.right,x)
    return node

def search(node,x):
    if node is None:
        return 'no'
    elif node.data == x:
        return 'yes'
    elif node.data > x:
        return search(node.left,x)
    else:
        return search(node.right,x)

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

    def insert(self,x):
        if self.root is None:
            self.root = Node(x)
        else:
            self.root = insert(self.root,x)
    
    def search(self,x):
        return search(self.root,x)

def mid_walk(node):
    if node is None:
        return 
    yield from mid_walk(node.left)
    yield node.data
    yield from mid_walk(node.right)

def pre_walk(node):
    if node is None:
        return 
    yield node.data
    yield from pre_walk(node.left)
    yield from pre_walk(node.right)


n = int(input())
bt = BST()
for line in sys.stdin:
    if line[0] == 'i':
        bt.insert(int(line[7:]))
    elif line[0] == 'f':
        print(bt.search(int(line[5:])))
    else:
        print(' '+' '.join(map(str,mid_walk(bt.root))))
        print(' '+' '.join(map(str,pre_walk(bt.root))))

Submission status: Accepted

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

class BinarySearchTree:
    def __init__(self):
        self.root = None
    
    def insert(self,key):
        node = Node(key, None)
        if self.root == None:
            self.root = node
        else:
            curr_node = self.root
            while curr_node:
                parent_node = curr_node
                if key < curr_node.val:
                    curr_node = curr_node.left
                else:
                    curr_node = curr_node.right
            node.parent = parent_node
            if key < parent_node.val:
                parent_node.left = node
            else:
                parent_node.right = node
     
    def find(self, key):
        if self.root == None:
            return False
        else:
            curr_node = self.root
            while curr_node:
                if key == curr_node.val:
                    return True
                elif key < curr_node.val:
                    curr_node = curr_node.left
                else:
                    curr_node = curr_node.right
            return False
            
        
        
        
    def preorderTraversal(self, node):
        result = []
        if node == None:
            return result
        result += [node.val]
        result += self.preorderTraversal(node.left)
        result += self.preorderTraversal(node.right)
        return result
        
    def inorderTraversal(self, node):
        result = []
        if node == None:
            return result
        result += self.inorderTraversal(node.left)
        result += [node.val]
        result += self.inorderTraversal(node.right)
        return result

N = int(input())
command = []
for i in range(N):
    command.append(tuple(input().split()))

T = BinarySearchTree()
for com in command:
    if com[0] == 'insert':
        T.insert(int(com[1]))
    if com[0] == 'find':
        flag = T.find(int(com[1]))
        if flag:
            print('yes')
        else:
            print('no')
    if com[0] == 'print':
        In = T.inorderTraversal(T.root)
        Pre = T.preorderTraversal(T.root)
        print(' ' + ' '.join(list(map(str, In))))
        print(' ' + ' '.join(list(map(str, Pre))))

Submission status: Accepted

Solution code:
nodes = None


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


def insert(z):
    global nodes
    y = None
    x = nodes

    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:
        nodes = z
    elif z.key < y.key:
        y.left = z
    else:
        y.right = z


def find(node, key):
    # if node is None:
    #     return "no"
    #
    # if node.key == key:
    #     return "yes"
    # elif node.key > key:
    #     return find(node.left, key)
    # else:
    #     return find(node.right, key)
    while node is not None and node.key != key:
        if node.key > key:
            node = node.left
        else:
            node = node.right

    if node is None:
        return "no"
    if node.key == key:
        return "yes"
    raise AssertionError()


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


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


def p(node):
    print("", " ".join([str(i) for i in get_inorder([], node)]))
    print("", " ".join([str(i) for i in get_preorder([], node)]))


n = int(input())
for _ in range(n):
    s = input().split()
    if s[0] == "insert":
        key = int(s[1])
        insert(Node(key=key))
    elif s[0] == "find":
        key = int(s[1])
        print(find(nodes, key))
    else:
        p(nodes)

Submission status: Accepted

Solution code:
# coding: utf-8

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

class NodeTree:
    def __init__(self, root=None):
        self.root = root
        
    def insert(self,z):
        y = None
        x = self.root
        while x != None:
            y = x
            if z.me < x.me:
                x = x.left
            else:
                x = x.right
        z.parent = y
        
        if y == None:
            self.root = z
        elif z.me < y.me:
            y.left = z
        else:
            y.right = z

    def find(self, z):
        y = None
        x = self.root
        while True:
            if x.me == z.me:
                return True
            elif x.me > z.me:
                if x.left != None:
                    x = x.left
                else:
                    return False
            else:
                if x.right != None:
                    x = x.right
                else:
                    return False
            
    
    def getPreorder(self, node, ans):
        ans.append(node)
        if node.left != None:
            self.getPreorder(node.left, ans)
        if node.right != None:
            self.getPreorder(node.right, ans)
            
    def getInorder(self, node, ans):
        if node.left != None:
            self.getInorder(node.left, ans)
        ans.append(node)
        if node.right != None:
            self.getInorder(node.right, ans)

        
def printAns(ans):
    for a in ans:
        print(" " + str(a.me),end="")
    print()
    
m = int(input().rstrip())
nt = NodeTree()
for i in range(m):
    line = input().rstrip().split()
    if line[0] == "insert":
        nt.insert(Node(int(line[1]),None,None))
    elif line[0] == "find":
        if nt.find(Node(int(line[1]),None,None)):
            print("yes")
        else:
            print("no")
    else:
        ans = []
        nt.getInorder(nt.root,ans)
        printAns(ans)
        ans = []
        nt.getPreorder(nt.root,ans)
        printAns(ans)

Submission status: Accepted

Solution code:
from sys import stdin

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

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

    def insert(self, v):
        cur = self.root
        cur_p = None
        while cur != None:
            cur_p = cur
            if v < cur.value:
                cur = cur.left
            elif v > cur.value:
                cur = cur.right

        n = Node(v, cur_p)
        if cur_p == None:
            self.root = n
        elif v < cur_p.value:
            cur_p.left = n
        else:
            cur_p.right = n

    def preorder(self):

        def rec_preorder(t=self.root):
            if t != None:
                print(" ", t.value, sep="", end="")
                rec_preorder(t.left)
                rec_preorder(t.right)

        rec_preorder()
        print()

    def inorder(self):

        def rec_inorder(t=self.root):
            if t != None:
                rec_inorder(t.left)
                print(" ", t.value, sep="", end="")
                rec_inorder(t.right)

        rec_inorder()
        print()

    def find(self, x):

        def rec_find(t=self.root):
            if t == None:
                return False
            elif x > t.value:
                return rec_find(t.right)
            elif x < t.value:
                return rec_find(t.left)
            else:
                return True

        return rec_find()

m = int(stdin.readline().rstrip())
t = BST()
for _ in range(m):
    q = stdin.readline().rstrip().split()
    if q[0] == "insert":
        t.insert(int(q[1]))
    elif q[0] == "find":
        if t.find(int(q[1])):
            print("yes")
        else:
            print("no")
    elif q[0] == "print":
        t.inorder()
        t.preorder()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys
sys.setrecursionlimit(10 ** 9)
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

from collections import defaultdict

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

root = None
nodes = defaultdict(lambda: None)

def insert(z):
    global root
    # yはxの親
    y = None
    x = root
    # zの親となるべきノードを探す
    while x is not None:
        y = x
        if z.key < x.key:
            # 左の子に移動
            x = nodes[x.left]
        else:
            # 右の子に移動
            x = nodes[x.right]
    if y is None:
        z.par = -1
    else:
        z.par = y.key
    
    if y is None:
        # Tが空の場合
        root = z
    elif z.key < y.key:
        # zをyの左の子にする
        y.left = z.key
    else:
        # zをyの右の子にする
        y.right = z.key

def find(key):
    if nodes[key]:
        print('yes')
    else:
        print('no')

def tree_walk(node):
    preo.append(node.key)
    if node.left != -1:
        tree_walk(nodes[node.left])
    ino.append(node.key)
    if node.right != -1:
        tree_walk(nodes[node.right])
    return

N = INT()

for _ in range(N):
    instr = input()
    if instr == 'print':
        preo = []
        ino = []
        tree_walk(root)
        print('', *ino)
        print('', *preo)
    elif instr.startswith('insert'):
        _, key = instr.split()
        key = int(key)
        node = Node(key)
        nodes[key] = node
        insert(node)
    else:
        _, key = instr.split()
        find(int(key))

Submission status: Accepted

Solution code:
class STNode:
    def __init__(self, k, l, r):
        self.key = k
        self.left = l
        self.right = r

def STinsert(h, z):
    p = None
    while True:
        if h.key == -1:
            break
        p = h
        if z.key < h.key:
            h = h.left
        else:
            h = h.right
    if z.key < p.key:
        p.left = z
    else:
        p.right = z

def STsearch(h, k):
    while h.key != -1:
        if k < h.key:
            h = h.left
        elif h.key < k:
            h = h.right
        else:
            print("yes")
            return
    print("no")

def preorder(head, h, A):
    if h.key == -1:
        return
    A.append(h.key)
    preorder(head, h.left, A)
    preorder(head, h.right, A)
    if head == h:
        print('', *A)

def inorder(head, h, B):
    if h.key == -1:
        return
    inorder(head, h.left, B)
    B.append(h.key)
    inorder(head, h.right, B)
    if head == h:
        print('', *B)

n = int(input())
NULLnode = STNode(-1, None, None)

first = list(input().split())
head = STNode(int(first[1]), NULLnode, NULLnode)
for i in range(n-1):
    temp = list(input().split())
    if temp[0] == "insert":
        z = STNode(int(temp[1]), NULLnode, NULLnode)
        STinsert(head, z)
    elif temp[0] == "print":
        A = []
        B = []
        inorder(head, head, B)
        preorder(head, head, A)
    else:
        STsearch(head, int(temp[1]))

Submission status: Accepted

Solution code:

class Node:

    def __init__(self, key: int) -> None:
        self.key = key
        self.parent = None
        self.left = None
        self.right = None


def input_line() -> (str, int):
    line = input().split()
    if line[0] == 'insert':
        return line[0], int(line[1])
    elif line[0] == 'find':
        return line[0], int(line[1])
    else:
        return line[0], None


def preorder(tree: Node) -> None:
    """先行順巡回。"""
    print(f' {tree.key}', end='')
    if tree.left is not None:
        preorder(tree.left)
    if tree.right is not None:
        preorder(tree.right)


def inorder(tree: Node) -> None:
    """中間順巡回。"""
    if tree.left is not None:
        inorder(tree.left)
    print(f' {tree.key}', end='')
    if tree.right is not None:
        inorder(tree.right)


def insert(new_node: Node) -> None:
    """二分探索木に挿入する。"""

    # rootはglobalに共有する。
    global root

    # new_nodeを付け加える節(parent)の初期値をNoneに設定する。
    parent = None

    # tmpにrootを設定する。
    tmp = root

    # new_nodeを付け加える節(parent)を探索する。
    while tmp is not None:
        parent = tmp
        if new_node.key < tmp.key:
            tmp = tmp.left
        else:
            tmp = tmp.right

    # new_nodeの親を設定する。
    new_node.parent = parent

    # new_nodeの子供を設定する。
    if parent is None:
        # treeが空だった場合は、rootにnew_nodeを設定する。
        root = new_node
    elif new_node.key < parent.key:
        parent.left = new_node
    else:
        parent.right = new_node


def find(key)-> bool:

    global root

    # tmpにrootを設定する。
    tmp = root

    # new_nodeを付け加える節(parent)を探索する。
    while tmp is not None:
        if key == tmp.key:
            return True
        elif key < tmp.key:
            tmp = tmp.left
        else:
            tmp = tmp.right

    return False


root = None  # treeの根を表す。初期値はNone。
N = int(input())
for _i in range(N):
    order, val = input_line()
    if order == 'insert':
        node = Node(val)
        insert(node)
    elif order == 'print':
        inorder(root)
        print()
        preorder(root)
        print()
    elif order == 'find':
        if find(val):
            print('yes')
        else:
            print('no')

Submission status: Accepted

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

    def __repr__(self):
        return str(self.key)

def insert(T, z):
    y = None
    x = T 
    while x != None:
        y = x
        if z.key < x.key:
            x = x.left
        else:
            x = x.right
    z.p = y
    #print(x,y,z)
    if y == None:
        #print("Y==None")
        T = z
        print(T)
    elif z.key<y.key:
        #print("z.key<y.key")
        y.left = z
    else:
        #print("z.key<y.key")
        y.right = z

def find(T, k):
    y = None
    x = T 
    while x != None:
        y = x
        if k == x.key:
            print('yes')
            return
        if k < x.key:
            x = x.left
        else:
            x = x.right
    print('no')
    


def printPreorder(x):
    if x == None:
        return
    printPreorder(x.left)
    print(end=' ')
    print(x,end='')
    printPreorder(x.right)

def printMidorder(x):
    if x == None:
        return
    print(end=' ')
    print(x,end='')
    printMidorder(x.left)
    printMidorder(x.right)

def printal(x):
    printPreorder(x)
    print()
    printMidorder(x)
    print()


N = int(input())
Q = input().split()
T = Node(int(Q[1]),None,None,None)
for i in range(N-1):
    Q = input().split()
    if Q[0] == "print":
        printal(T)
        continue
    elif Q[0] == "find":
        find(T,int(Q[1]))
        continue
    insert(T,Node(int(Q[1]),None,None,None))

Submission status: Accepted

Solution code:
def insert(z):
    global root
    y = NIL
    x = root
    #print(x)
    while x != NIL:
        y = x
        if z < x:
            x = TL[x]
        else:
            x = TR[x]
    TP[z] = y

    if y == NIL:
        root = z
    elif z < y:
        TL[y] = z
    else:
        TR[y] = z


def inorder(u):
    if u == NIL:
        return
    inorder(TL[u])
    print(' ', end='')
    print(u, end='')
    inorder(TR[u])


def preorder(v):
    if v == NIL:
        return
    print(' ', end='')
    print(v, end='')
    preorder(TL[v])
    preorder(TR[v])


TR = {}
TL = {}
TP = {}
NIL = None
root = NIL
m = int(input())
data = [input().split() for _ in range(m)]
#print(data)
for i in data:
    if i[0][0] == 'i':
        TR[int(i[1])] = TL[int(i[1])] = NIL
        insert(int(i[1]))
    elif i[0][0] == 'f':
        if int(i[1]) in TR:
            print('yes')
        else:
            print('no')
    else:
        inorder(root)
        print()
        preorder(root)
        print()

Submission status: Accepted

Solution code:
import sys


class Node:
    __slots__ = ['key', 'parent', 'left', 'right']

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


def insert(root, z):
    if root is None:
        return z

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

    return root


def find(node, key):
    if not node:
        return False

    if key < node.key:
        return find(node.left, key)
    if key > node.key:
        return find(node.right, key)

    return True  # key == node.key


def inorder(node):
    if not node:
        return
    yield from inorder(node.left)
    yield node.key
    yield from inorder(node.right)


def preorder(node):
    if not node:
        return
    yield node.key
    yield from preorder(node.left)
    yield from preorder(node.right)


def print_tree(root):
    print(''.join(' ' + str(key) for key in inorder(root)))
    print(''.join(' ' + str(key) for key in preorder(root)))


root = None

n = int(sys.stdin.readline())
for _ in range(n):
    command, *args = sys.stdin.readline().split()
    if command == 'insert':
        root = insert(root, Node(int(args[0])))
    elif command == 'find':
        print('yes' if find(root, int(args[0])) else 'no')
    else:
        print_tree(root)