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: Runtime Error

Solution code:
from io import StringIO

class BinaryTree:

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


    def __init__(self):
        self.root = None
        self.output = StringIO()

    def insert(self, key):
        if self.root is None:
            self.root = self.Node(key)
        else:
            root = self.root
            temp = None
            while True:
                temp = root
                if key > root.key:
                    root = root.right
                    if root is None:
                        temp.right = self.Node(key)
                        break
                else:
                    root = root.left
                    if root is None:
                        temp.left = self.Node(key)
                        break

    def ini_print_inorder(self):
        self.output = StringIO()
        self.print_inorder(self.root)
        return self.output.getvalue()

    def ini_print_preorder(self):
        self.output = StringIO()
        self.print_preorder(self.root)
        return self.output.getvalue()

    def print_inorder(self, node):
        if node is not None:
            self.print_inorder(node.left)
            print(node.key, end = " ", file = self.output)
            self.print_inorder(node.right)

    def print_preorder(self, node):
        if node is not None:
            print(node.key, end = " ", file = self.output)
            self.print_preorder(node.left)
            self.print_preorder(node.right)

    def test_insert(self, keys):
        for k in keys:
            self.insert(k)

    def ini_find(self, key):
        print(self.find(key))

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


length = int(input())
b = BinaryTree()
for _ in range(length):
    comm = input()
    if comm[0] == "i":
        com, num = comm.split(" ")
        b.insert(int(num))
    elif comm[0] == "p":
        print(" ", end = "")
        print((b.ini_print_inorder())[:-1])
        print(" ", end = "")
        print(b.ini_print_preorder()[:-1])
    else:
        com, num = comm.split(" ")
        b.ini_find(num)

Submission status: Runtime Error

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

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

def insert(z):
    global 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 y is None:
        root = z
    elif z.key < y.key:
        y.left = z
    else:
        y.right = z

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

def pre_order(node):
    if node is not None:
        print node.key,
        pre_order(node.left)
        pre_order(node.right)

def in_order(node):
    if node is not None:
        in_order(node.left)
        print node.key,
        in_order(node.right)

m = int(raw_input())
root = None
for i in range(m):
    line = map(str, raw_input().split())
    if line[0] == "insert":
        z = Node_Class(int(line[1]), None, None, None)
        insert(z)
    elif line[0] == "find":
        find(int(line[1]))
    else:
        print "".
        in_order(root)
        print
        print "",
        pre_order(root)
        print

Submission status: Runtime Error

Solution code:
class Tree:
    def __init__(self, orders):
        self.root = None
        for order in orders:
            if len(order) == 1:
                self.inorder_print()
                self.preorder_print()
            else:
                if len(order[0]) == 4:
                    self.find(int(order[1]))
                else:
                    self.insert(int(order[1]))

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

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

    def inorder_print(self):
        self.root.inorder_print()
        print()

    def preorder_print(self):
        self.root.preorder_print()
        print()


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

    def find(self, key):
        k = self.key
        if key == k:
            print('yes')
        elif key < k:
            if self.left:
                self.left.find(key)
            else:
                print('no')
        else:
            if self.right:
                self.right.find(key)
            else:
                print('no')

    def inorder_print(self):
        if self.left:
            self.left.inorder_print()
        print(' {}'.format(self.key), end='')
        if self.right:
            self.right.inorder_print()

    def preorder_print(self):
        print(' {}'.format(self.key), end='')
        if self.left:
            self.left.preorder_print()
        if self.right:
            self.right.preorder_print()


if __name__ == '__main__':
    import sys
    m = int(input())
    orders = [line.strip().split() for line in sys.stdin]
    Tree(orders)

Submission status: Runtime Error

Solution code:
import sys

tree={}
np = -1

home=0
tree[home]=[None, None, None]

def search(p, x):
    while p != None:
        tmp = tree[p]
        if tmp[0] == x: return True
        if x < tmp[0]:
            p = tmp[1]
        else:
            p = tmp[2]
    return False

def node(x):
    global np
    np += 1
    tree[np] = [x, None, None]
    return np

def insert(p, x):
    if p == None or np == -1: return node(x)
    tmp = tree[p]
    if x== tmp[0]: return p
    elif x<tmp[0]:
        tree[p][1]=insert(tmp[1],x)
    else:
        tree[p][2]=insert(tmp[2],x)
    return p

def preorder(p):
    if p == None: return []
    p1, p2 = tree[p][1:3]
    return [tree[p][0]] + preorder(p1) + preorder(p2)

def inorder(p):
    if p == None: return []
    p1, p2 = tree[p][1:3]
    return inorder(p1) + [tree[p][0]] +inorder(p2)

n = int(input())
i = 0
while i<n:
    s = raw_input()
    if s[0]=='i':
        insert(0,int(s[7:]))
    elif s[0]=='f':
        if search(0,int(s[5:])): print 'yes'
        else print 'no'
    elif s[0]=='p':
        print ' ' + ' '.join(map(str, inorder(home)))
        print ' ' + ' '.join(map(str, preorder(home)))
    i += 1

Submission status: WA: Presentation Error

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Mar  2 17:11:49 2019

@author: Yamazaki Kenichi
"""

m = int(input())
A = [list(input().split()) for i in range(m)]

T = [[-1,-1,-1,-1]]
def insert(T,u,x):
    if T[0][3] == -1:
        T[0][3] = x
        return
    if x < T[u][3]:
        if T[u][1] == -1:
            T[u][1] = len(T)
            T.append([u,-1,-1,x])
        else:
            insert(T,T[u][1],x)
    else:
        if T[u][2] == -1:
            T[u][2] = len(T)
            T.append([u,-1,-1,x])
        else:
            insert(T,T[u][2],x)
def ino(u):
    if T[u][1] != -1:
        ino(T[u][1])
    ino_res.append(str(T[u][3]))
    if T[u][2] != -1:
        ino(T[u][2])
def pre(u):
    pre_res.append(str(T[u][3]))
    if T[u][1] != -1:
        pre(T[u][1])
    if T[u][2] != -1:
        pre(T[u][2])
def find(u,x):
    if x == T[u][3]:
        return True
    elif x < T[u][3]:
        if T[u][1] == -1:
            return False
        return find(T[u][1],x)
    else:
        if T[u][2] == -1:
            return False
        return find(T[u][2],x)
for c in A:
    if c[0] == 'insert':
        insert(T,0,int(c[1]))
    elif c[0] == 'find':
        print('yes') if find(0,int(c[1])) else print('no')
    else:
        ino_res = []
        ino(0)
        pre_res = []
        pre(0)
        print(' '.join(ino_res))
        print(' '.join(pre_res))

Submission status: WA: Presentation Error

Solution code:
m = int(input())

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


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

    def getRoot(self):
        return self.root
    def setRoot(self, v):
        self.root = v

    def inorder(self, v=None):
        if v is None:
            v = self.root
        if v.left is not None:
            self.inorder(v.left)
        print(' ' + str(v.key), end='')
        if v.right is not None:
            self.inorder(v.right)
        
    def preorder(self, v=None):
        if v is None:
            v = self.root
        print(' ' + str(v.key), end='')
        if v.left is not None:
            self.preorder(v.left)
        if v.right is not None:
            self.preorder(v.right)

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

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

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


T = BinaryTree()

for i in range(m):
    inp = input().split()
    if inp[0] == 'print':
        T.inorder()
        print()
        T.preorder()
    elif inp[0] == 'find':
        find(T, int(inp[1]))
    else:
        v = Node(int(inp[1]), None, None)
        insert(T, v)

Submission status: WA: Presentation Error

Solution code:
#coding:utf-8
N = int(input())
trees = [list(input().split()) for i in range(N)]

class BinaryTree:
    def __init__(self,key,p=None,l=None,r=None):
        self.key = key
        self.p = p
        self.l = l
        self.r = r

def Insert(root,z):
    y = None
    x = root
    while x != None:
        y = x
        if z.key < x.key:
            x = x.l
        else:
            x = x.r
    z.p = y

    if y == None:
        root = z
    elif z.key < y.key:
        y.l = z
    else:
        y.r = z
    return root

def preOrder(x):
    if x == None:
        return
    global preList
    preList.append(x.key)
    
    preOrder(x.l)
    preOrder(x.r)

def inOrder(x):
    if x == None:
        return
    inOrder(x.l)

    global inList
    inList.append(x.key)
    
    inOrder(x.r)

def Find(x,target):
    if x == None:
        return 
    if x.key == target:
        global yes
        yes = True
        return True
    Find(x.l,target)
    Find(x.r,target)

root = None
for data in trees:
    if data[0] == "insert":
        z = BinaryTree(int(data[1]))
        root = Insert(root,z)
    if data[0] == "find":
        yes = False
        a = Find(root, int(data[1]))
        if yes:
            print("yes")
        else:
            print("no")
        
    if data[0] == "print":
        inList = []
        preList = []
        inOrder(root)
        a = " ".join([str(num) for num in inList])
        print(a)

        preOrder(root)
        a = " ".join([str(num) for num in preList])
        print(a)