Problem:

Binary Search Tree III

Write a program which performs the following operations to a binary search tree $T$ by adding delete operation to B: Binary Search Tree II.

  
insert  $k$: Insert a node containing $k$ as key into $T$.

  
find $k$: Report whether $T$ has a node containing $k$. 

  
delete $k$: Delete a node containing $k$.

  
print: Print the keys of the binary search tree by inorder tree walk and  preorder tree walk respectively.

The operation delete $k$ for deleting a given node $z$ containing key $k$ from $T$ can be implemented by an algorithm which considers the following cases:

 If $z$ has no children, we modify its parent $z.p$ to replace $z$ with NIL as its child (delete $z$).

 If $z$ has only a single child, we "splice out" $z$ by making a new link between its child and its parent.

 If $z$ has two children, we splice out $z$'s successor $y$ and replace $z$'s key with $y$'s key.

Input

   In the first line, the number of operations $m$ is given. In the following $m$ lines, operations represented by insert $k$, find $k$, delete $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

18
insert 8
insert 2
insert 3
insert 7
insert 22
insert 1
find 1
find 2
find 3
find 4
find 5
find 6
find 7
find 8
print
delete 3
delete 7
print

Sample Output 1

yes
yes
yes
no
no
no
yes
yes
 1 2 3 7 8 22
 8 2 1 3 7 22
 1 2 8 22
 8 2 1 22

Reference

Introduction to Algorithms, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. The MIT Press.



Sample input:
18
insert 8
insert 2
insert 3
insert 7
insert 22
insert 1
find 1
find 2
find 3
find 4
find 5
find 6
find 7
find 8
print
delete 3
delete 7
print


Sample output:
yes
yes
yes
no
no
no
yes
yes
 1 2 3 7 8 22
 8 2 1 3 7 22
 1 2 8 22
 8 2 1 22

Submission status: Accepted

Solution code:
# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_8_C
# Binary Search Tree III
# Result:
import sys

class BinarySearchTree(object):
    def __init__(self):
        super(BinarySearchTree, self).__init__()
        self.root = None
        self.count = 0

    def insert(self, val):
        node = Node(val)
        y = None
        x = self.root
        while x != None:
            y = x
            if node.id_ < x.id_:
                x = x.left
            else:
                x = x.right
        node.parent = y

        if y == None:
            self.root = node
        elif node.id_ < y.id_:
            y.left = node
        else:
            y.right = node

    def find(self, val):
        x = self.root
        while x != None:
            if val == x.id_:
                break
            elif val < x.id_:
                x = x.left
            else: # val > x.id_
                x = x.right
        if x != None:
            return True
        else:
            return False

    def delete(self, val):
        p = None
        x = self.root
        while x != None:
            if val == x.id_:
                break
            p = x
            if val < x.id_:
                x = x.left
            else: # val > x.id_
                x = x.right
        if x != None:
            if x.left != None and x.right != None:
                next_ = self._next_node_in_inorder(x)
                x.id_ = next_.id_
                x = next_
                p = next_.parent
            if x.left == None and x.right == None:
                if x == self.root:
                    self.root = None
                else:
                    if p.left == x:
                        p.left = None
                    else: #p.right == x
                        p.right = None
            elif x.left == None: # x.right != None
                x.right.parent = p
                if p != None:
                    if p.left == x:
                        p.left = x.right
                    else:
                        p.right = x.right
                else: # x == self.root
                    self.root = x.right
            elif x.right == None: # x.left != None
                x.left.parent = p
                if p != None:
                    if p.left == x:
                        p.left = x.left
                    else:
                        p.right = x.left
                else: # x == self.root
                    self.root = x.left
            else:
                assert True

    def _next_node_in_inorder(self, node):
        x = node.right
        while x.left != None:
            x = x.left
        return x

    def __str__(self):
        return 'Call to_inorder_walk() or to_preorder_walk()'

    def to_inorder_walk(self):
        return self._to_inorder_walk(self.root)

    def to_preorder_walk(self):
        return self._to_preorder_walk(self.root)

    def _to_inorder_walk(self, node):
        if node == None: return ''
        str_ = self._to_inorder_walk(node.left)
        str_ += ' %d' % (node.id_)
        str_ += self._to_inorder_walk(node.right)
        return str_

    def _to_preorder_walk(self, node):
        if node == None: return ''
        str_ = ' %d' % (node.id_)
        str_ += self._to_preorder_walk(node.left)
        str_ += self._to_preorder_walk(node.right)
        return str_

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

    def __str__(self):
        str_ = '%d' % (self.id_)
        return str_


bst = BinarySearchTree()

_nops = int(sys.stdin.readline())
for _ in range(0, _nops):
    op = sys.stdin.readline().rstrip().split(' ')
    if op[0] == 'insert':
        bst.insert(int(op[1]))
    elif op[0] == 'print':
        print bst.to_inorder_walk()
        print bst.to_preorder_walk()
    elif op[0] == 'find':
        if bst.find(int(op[1])):
            print 'yes'
        else:
            print 'no'
    elif op[0] == 'delete':
        bst.delete(int(op[1]))
    else:
        pass

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_8_A&lang=jp
# cat alds1_8_c.txt | ./alds1_8_c.py

import sys


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


def insert(key, node):
    """
    ??????????????????????????????, ???????????°???????????? node.left ????????? node.right ?????????????????????
    """
    if key < node.key:
        if node.left is None:
            left_node = Node(key, node)
            node.left = left_node
        else:
            insert(key, node.left)
    else:
        if node.right is None:
            right_node = Node(key, node)
            node.right = right_node
        else:
            insert(key, node.right)


def find(key, node):
    """
    ??????????????????????????????, ?????????????????¨????????°?????????????????????????????´?????????
    ????????????????????§??????????????????????????????????????¨??????????????° None ????????????
    """
    if key == node.key:
        return node
    elif key < node.key:
        if node.left is None:
            return None
        else:
            return find(key, node.left)
    else:
        if node.right is None:
            return None
        else:
            return find(key, node.right)


def print_preorder(node):
    print(" %d" % 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):
    if node.left is not None:
        print_inorder(node.left)
    print(" %d" % node.key, end="")
    if node.right is not None:
        print_inorder(node.right)


def search_minimum_node(node):
    """
    node ???????????¨??????(??¨???)??¨??????????°????????????????????????????????????????
    ?????? node ??????????????±????????´??? leaf ?????¢?´¢??????????????§?????????
    """
    if node.left is not None:
        return search_minimum_node(node.left)
    else:
        return node


def delete(node):
    if node.left is None and node.right is None:
        # ?????? node ??????????????§, ?????? parent ???????????§??§????????????????????????
        if node.parent.left is node:
            node.parent.left = None
        else:
            node.parent.right = None
    elif node.left is None and node.right is not None:
        # node ??????????????????????????§, node ????????? node ????????????????????§?????????????????????
        # node ??????????????? node ???????????????????????¨???????????§?????????????????????
        if node is node.parent.left:
            # node ?????????????????????
            node.parent.left = node.right
        else:
            # node ?????????????????????
            node.parent.right = node.right
        node.right.parent = node.parent
    elif node.left is not None and node.right is None:
        # node ??????????????????????????§, node ????????? node ????????????????????§?????????????????????
        # node ??????????????? node ???????????????????????¨???????????§?????????????????????
        if node is node.parent.left:
            # node ?????????????????????
            node.parent.left = node.left
        else:
            # node ?????????????????????
            node.parent.right = node.left
        node.left.parent = node.parent
    else:
        # ????????????????????????????????????
        # ?¬??????? (successor) ????¨??????????
        successor = search_minimum_node(node.right)
        if successor.right is not None:
            # ??????????¬???????????????´??? node ???????????´???, ?????????????????????????????????
            successor.right.parent = successor.parent
            successor.parent.left = successor.right
        else:
            # ?¬???????????????´??? node ???????????´???, ?¬????????????????????????????????????????
            if successor.parent.left is successor:
                successor.parent.left = None
            else:
                successor.parent.right = None
        # node ??????????¬???????????????§???????????????
        node.key = successor.key


def main():
    lines = sys.stdin.readlines()
    root = Node()

    for order in lines[1:]:
        if order.startswith("insert"):
            _, key = order.strip().split(" ")
            key = int(key)
            if root.key is None:
                root.key = key
            else:
                insert(key, root)
        elif order.startswith("find"):
            _, key = order.strip().split(" ")
            fild_result = "no" if find(int(key), root) is None else "yes"
            print(fild_result)
        elif order.startswith("print"):
            print_inorder(root)
            print("")
            print_preorder(root)
            print("")
        elif order.startswith("delete"):
            _, key = order.strip().split(" ")
            node = find(int(key), root)  # ????????§ node ???????????????????????£?????¨???????????????????§???§????????????
            delete(node)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from __future__ import print_function
from sys import stdin
class Node:
    def __init__(self, id):
        self.id = id
        self.left = None
        self.right = None
        self.parent = None

def preorder_tree_walk(root):
    print('', root.id, end='')
    if root.left != None:
        preorder_tree_walk(root.left)
    if root.right != None:
        preorder_tree_walk(root.right)

def inorder_tree_walk(root):
    if root.left != None:
        inorder_tree_walk(root.left)
    print('', root.id, end='')
    if root.right != None:
        inorder_tree_walk(root.right)

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

    if y == None:
        root = z
    elif z.id < y.id:
        y.left = z
    else:
        y.right = z
    return root

def find(root, x):
    while root != None and x != root.id:
        if x < root.id:
            root = root.left
        else:
            root = root.right
    return root

def delete(root, z):
    # detect delete node y.
    if  z.left == None or z.right == None:
        y = z
    else:
        y = get_successor(z)

    # detect y's child x
    if y.left != None:
        x = y.left
    else:
        x = y.right

    if x != None:
        x.parent = y.parent

    if y.parent == None:
        root = x
    elif y == y.parent.left:
        y.parent.left = x
    else:
        y.parent.right = x

    if y != z:
        z.id = y.id


def get_successor(x):
    if x.right != None:
        return get_minimum(x.right)

    y = x.parent
    while y != None and x == y.right:
        x = y
        y = y.parent
    return y

def get_minimum(x):
    while x.left != None:
        x = x.left
    return x


n = int(raw_input())
root = None
for i in xrange(n):
    cmd = stdin.readline()
    if cmd.startswith('i'):
        num = int(cmd[7:])
        root = insert(root, Node(num))
    elif cmd.startswith('p'):
        inorder_tree_walk(root)
        print()
        preorder_tree_walk(root)
        print()
    elif cmd.startswith('d'):
        num = int(cmd[7:])
        node = find(root, num)
        if node != None:
            delete(root, node)
    else:
        # find
        num = int(cmd[5:])
        if find(root, num) != None:
            print('yes')
        else:
            print('no')

Submission status: Accepted

Solution code:
def insert(tree,k):
    y = None
    x = tree
    z = {'key':k, 'parent':None, 'left':None, 'right':None}
    while x != None:
        y = x
        if x['key'] > k:
            x = x['left']
        else:
            x = x['right']
    z['parent'] = y
    if y == None:
        tree = z
    elif y['key'] > k:
        y['left'] = z
    else:
        y['right'] = z
    return tree

def delete_leaf(p,x):
    if left(p,x):
        p['left'] = None
    else:
        p['right'] = None
    return p

def delete_half_leaf(p,x,y):
    if left(p,x):
        p['left'] = y
    else:
        p['right'] = y
    y['parent'] = p
    return p


def left(p,x):
    if p['left'] != None and p['left']['key'] == x['key']:
        return True
    else:
        return False

def delete_internal(p,x):
    y = x['right']
    while y['left'] != None:
        y = y['left']
    x['key'] = y['key']
    if y['right'] == None:
        y['parent'] = delete_leaf(y['parent'],y)
    else:
        y['parent'] = delete_half_leaf(y['parent'],y,y['left'])
    return p

def delete(tree,k):
    x = find(tree,k)
    if x == None: return
    p = x['parent']
    if p == None:
        pass
    else:
        if x['left'] == x['right'] == None:
            p = delete_leaf(p,x)
        elif x['right'] == None:
            p = delete_half_leaf(p,x,x['left'])
        elif x['left'] == None:
            p = delete_half_leaf(p,x,x['right'])
        else:
            p = delete_internal(p,x)
    return tree

def find(tree,k):
    x = tree
    while x != None:
        if x['key'] == k:
            return x
        elif x['key'] > k:
            x = x['left']
        else:
            x = x['right']
    return None

def middleorder(x):
    if x != None:
        middleorder(x['left'])
        print x['key'],
        middleorder(x['right'])

def preorder(x):
    if x != None:
        print x['key'],
        preorder(x['left'])
        preorder(x['right'])



tree = None
m = int(raw_input())
for i in range(m):
    c = raw_input().strip()
    if c[0] == 'i':
        tree = insert(tree, int(c[7:]))
    elif c[0] == 'f':
        x = find(tree, int(c[5:]))
        if x == None:
            print "no"
        else:
            print "yes"
    elif c[0] == 'd':
        tree = delete(tree, int(c[7:]))
    elif c[0] == 'p':
        print '',
        middleorder(tree)
        print
        print '',
        preorder(tree)
        print

Submission status: Accepted

Solution code:
def insert(tree,k):
    y = None
    x = tree
    z = {'key':k, 'parent':None, 'left':None, 'right':None}
    while x != None:
        y = x
        if x['key'] > k:
            x = x['left']
        else:
            x = x['right']
    z['parent'] = y
    if y == None:
        tree = z
    elif y['key'] > k:
        y['left'] = z
    else:
        y['right'] = z
    return tree

def get_successor(x):
    if x['right'] != None:
        return get_minimum(x['right'])
    else:
        y = x['parent']
        while y != None and x == y['left']:
            x = y
            y = y['parent']
        return y

def get_minimum(x):
    while x['left'] != None:
        x = x['left']
    return x

def delete_node(tree,z):
    if z['left'] == None or z['right'] == None:
        y = z
    else:
        y = get_successor(z)

    if y['left'] != None:
        x = y['left']
    else:
        x = y['right']

    if x != None:
        x['parent'] = y['parent']

    if y['parent'] == None:
        tree = x
    else:
        if y['parent']['left'] != None and y['parent']['left']['key'] == y['key']:
            y['parent']['left'] = x
        else:
            y['parent']['right'] = x

    z['key'] = y['key']

    return tree

def find(tree,k):
    x = tree
    while x != None:
        if x['key'] == k:
            return x
        elif x['key'] > k:
            x = x['left']
        else:
            x = x['right']
    return None

def middleorder(x):
    if x != None:
        middleorder(x['left'])
        print x['key'],
        middleorder(x['right'])

def preorder(x):
    if x != None:
        print x['key'],
        preorder(x['left'])
        preorder(x['right'])



tree = None
m = int(raw_input())
for i in range(m):
    c = raw_input().strip()
    if c[0] == 'i':
        tree = insert(tree, int(c[7:]))
    elif c[0] == 'f':
        x = find(tree, int(c[5:]))
        if x == None:
            print "no"
        else:
            print "yes"
    elif c[0] == 'd':
        z = find(tree, int(c[7:]))
        if not z == None: tree = delete_node(tree,z)
    elif c[0] == 'p':
        print '',
        middleorder(tree)
        print
        print '',
        preorder(tree)
        print

Submission status: Accepted

Solution code:
class Tree:
    root = None

    def insert(self, node):
        y = None
        x = self.root
        while x:
            y = x
            x = x.left if node.key < x.key else x.right
        node.parent = y

        if not y:
            self.root = node
        elif node.key < y.key:
            y.left = node
        else:
            y.right = node

    def find_node(self, value):
        return self.root.find(value)

    def find(self, value):
        print('yes' if self.find_node(value) else 'no')

    def delete(self, value):
        self.find_node(value).delete()

    def print(self):
        print(' ', end='')
        print(*self.root.print_in())
        print(' ', end='')
        print(*self.root.print_pre())


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

    def find(self, value):
        diff = self.key - value
        if diff == 0:
            return self
        elif diff > 0:
            return self.left and self.left.find(value)
        else:
            return self.right and self.right.find(value)

    def delete(self):
        left, right = self.left, self.right
        if not left and not right:
            self.delete_connect(self.parent, None)
        elif left and not right:
            self.delete_connect(self.parent, left)
        elif not left and right:
            self.delete_connect(self.parent, right)
        else:
            next_node = right.get_leftmost()
            self.key = next_node.key
            next_node.delete()

    def delete_connect(self, parent, child):
        if parent:
            if parent.key > self.key:
                parent.left = child
            else:
                parent.right = child
        if child:
            child.parent = parent

    def get_leftmost(self):
        if self.left:
            return self.left.get_leftmost()
        return self

    def print_pre(self):
        yield self.key
        if self.left:
            for k in self.left.print_pre(): yield k
        if self.right:
            for k in self.right.print_pre(): yield k

    def print_in(self):
        if self.left:
            for k in self.left.print_in(): yield k
        yield self.key
        if self.right:
            for k in self.right.print_in(): yield k


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

while m:
    l = input()
    f = l[0]
    if f == 'i':
        tree.insert(Node(int(l.split()[1])))
    elif f == 'f':
        tree.find(int(l.split()[1]))
    elif f == 'd':
        tree.delete(int(l.split()[1]))
    else:
        tree.print()
    m -= 1

Submission status: Accepted

Solution code:
#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin
   
   
class Node(object):
    def __init__(self, key=None):
        self.key = key
        self.parent = None
        self.left = None
        self.right = None
   
   
def tree_insert(top, z):
    y = None
    x = top
    while isinstance(x, Node):
        y = x
        if z.key < x.key:
            x = x.left
        else:
            x = x.right
    z.parent = y
    if y is None:
        top = z
    elif z.key < y.key:
        y.left = z
    else:
        y.right = z
    return top
   
def tree_find(top, k):
    x = top
    while x != None and k != x.key:
        if k < x.key:
            x = x.left
        else:
            x = x.right
    return x

def deleteNode(top, z):#(top, Node())
    if z.left == None or z.right == None:
        y = z
    else:
        y = getSuccessor(z)

    if y.left != None:
        x = y.left
    else:
        x = y.right

    if x != None:
        x.parent = y.parent

    if y.parent == None:
        top = x
    elif y == y.parent.left:
        y.parent.left = x
    else:
        y.parent.right = x

    if y != z:
        z.key = y.key
    return top

def getSuccessor(x):
    if x.right != None:
        return getMinimum(x.right)

    y = x.parent
    while y != None and x == y.right:
        x = y
        y = y.parent
    return y

def getMinimum(x):
    while x.left != None:
        x = x.left
    return x


def inorder_walk(node):
    if node.left:
        inorder_walk(node.left)
    print('', node.key, end='')
    if node.right:
        inorder_walk(node.right)
   
   
def preorder_walk(node):
    print('', node.key, end='')
    if node.left:
        preorder_walk(node.left)
    if node.right:
        preorder_walk(node.right)
   
   
n = int(stdin.readline())
   
top = None
for _ in range(n):
    cmd = stdin.readline()
    if cmd.startswith('i'):
        key = int(cmd[7:])
        #assert -2000000000 <= key <= 2000000000
        top = tree_insert(top, Node(key))
    elif cmd.startswith('f'):
        key = int(cmd[5:])
        if tree_find(top, key) != None:
            print('yes')
        else:
            print('no')
    elif cmd.startswith('d'):
        key = int(cmd[7:])
        top = deleteNode(top, tree_find(top, key))
    else:
        inorder_walk(top)
        print()
        preorder_walk(top)
        print()

Submission status: Accepted

Solution code:
class BinarySearchTree:
    root = None
    def insert(self, k):
        y = None
        x = self.root
        z = Node(k)
        while x:
            y = x
            if z.k < x.k:
                x = x.l
            else:
                x = x.r
        z.p = y
         
        if y == None:
            self.root = z
        else:
            if z.k < y.k:
                y.l = z
            else:
                y.r = z
                
    def find(self, x, k):
        while x != None and k != x.k:
            if k < x.k:
                x = x.l
            else:
                x = x.r
        return x
     
    def deleteNode(self, z):
        y = None
        x = None
        if z.l == None or z.r == None:
            y = z
        else:
            y = self.getSuccessor(z)
        
        if y.l != None:
            x = y.l
        else:
            x = y.r
        
        if x != None:
            x.p = y.p
        
        if y.p == None:
            self.root = x
        else:
            if y == y.p.l:
                y.p.l = x
            else:
                y.p.r = x
        
        if y != z:
            z.k = y.k

    def getSuccessor(self, x):
        if x.r != None:
            return self.getMinimum(x.r)
        y = x.p
        while y != None and x == y.r:
            x = y
            y = y.p
        return y
    
    def getMinimum(self, x):
        while x.l != None:
            x = x.l
        return x
    
    def preParse(self, u):
        if u == None:
            return
        print("", str(u.k), end = "")
        self.preParse(u.l)
        self.preParse(u.r)
 
    def inParse(self, u):
        if u == None:
            return
        self.inParse(u.l)
        print("", str(u.k), end = "")
        self.inParse(u.r)
 
class Node: 
    def __init__(self, k):
        self.k = k
        self.p = None
        self.l = None
        self.r = None
 
if __name__ == '__main__':
    n = int(input().rstrip())
    x = BinarySearchTree()
    for i in range(n):
        com = input().rstrip()
        if com.startswith("insert"):
            k = int(com.split(" ")[1])
            x.insert(k)
        elif com.startswith("find"):
            k = int(com.split(" ")[1])
            if x.find(x.root, k) != None:
                print("yes")
            else:
                print("no")
        elif com.startswith("delete"):
            k = int(com.split(" ")[1])
            x.deleteNode(x.find(x.root, k))
        else:
            x.inParse(x.root)
            print()
            x.preParse(x.root)
            print()

Submission status: Accepted

Solution code:
class BinarySearchTree:
    def __init__(self):
        self.root = None
    def show_keys(self):
        in_order_from(self.root)
        print('')
        pre_order_from(self.root)
        print('')
    def insert(self, key):
        node = Node(key)
        insert(self, node)
    def find(self, key):
        if find_from(self.root, key):
            print('yes')
        else:
            print('no')
    def delete_key(self, key):
        node = find_from(self.root, key)
        delete_node(self, node)

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.root
    while x != None:
        y = x
        if z.key < x.key:
            x = x.left
        else:
            x = x.right
    z.parent = y
    if y == None:
        T.root = z
    elif z.key < y.key:
        y.left = z
    else:
        y.right = z

def delete_node(T, node):
    if node.left and node.right:
        x = node.right
        while x.left:
            x = x.left
        node.key = x.key
        delete_node(T, x)
    elif node.left or node.right:
        child = node.left or node.right
        if node is T.root:
            T.root = child
            child.parent = None
        else:
            if node.parent.left is node:
                node.parent.left = child
                child.parent = node.parent
            else:
                node.parent.right = child
                child.parent = node.parent
    else:
        if node.parent.left is node:
            node.parent.left = None
        else:
            node.parent.right = None

def in_order_from(node):
    if node:
        in_order_from(node.left)
        print(' {0}'.format(node.key), end = '')
        in_order_from(node.right)

def pre_order_from(node):
    if node:
        print(' {0}'.format(node.key), end = '')
        pre_order_from(node.left)
        pre_order_from(node.right)

def find_from(node, k):
    while node:
        if node.key == k:
            return node
        if k < node.key:
            node = node.left
        else:
            node = node.right


import sys

t = BinarySearchTree()

m = sys.stdin.readline()

for i in sys.stdin.readlines():
    if i[0] == 'i':
        t.insert(int(i[7:]))
    elif i[0] == 'f':
        t.find(int(i[5:]))
    elif i[0] == 'd':
        t.delete_key(int(i[7:]))
    else:
        t.show_keys()

Submission status: Accepted

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

def insert(T,z):
    x=T
    y=None
    while isinstance(x,node):
        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 find(T,z):
    if T is None:
        return False
    else:
        y=None
        x=T
        while 1:
            y=x
            if x is None:
                return False
            elif z.key==x.key:
                return True
            elif z.key<x.key:
                x=x.left
            else:
                x=x.right
                
def delete(T,z,i):
    if i==0:
        x=T
        y=None
        while 1:    
            y=x
            if x is None:
                return 
            elif z.key==x.key:
                break
            elif z.key<x.key:
                x=x.left
            else:
                x=x.right
            z.parent=y
        z=x     
    if z.left is None and z.right is None:
        if z is z.parent.right:
            z.parent.right=None
        else:
            z.parent.left=None
    elif z.left is None:
        if z is z.parent.left:
            z.parent.left=z.right
            z.right.parent=z.parent
        else:
            z.parent.right=z.right
            z.right.parent=z.parent
    elif z.right is None:
        if z is z.parent.left:
            z.parent.left=z.left
            z.left.parent=z.parent
        else:
            z.parent.right=z.left
            z.left.parent=z.parent
    else:
        y=del_inorder(z.right)
        z.key=y.key
        delete(T,y,1)
           
def preorder(u):
    if u is None:
        return
    pripre.append(str(u.key))
    preorder(u.left)
    preorder(u.right)

def inorder(u):
    if u is None:
        return
    inorder(u.left)
    priin.append(str(u.key))
    inorder(u.right)
    
def del_inorder(u):
    if u is None:
        return
    del_inorder(u.left)
    Min.append(u)
    del_inorder(u.right)
    return Min[0]

m=input()
root=None
for i in xrange(m):
    cmd=map(str,raw_input().split())
    if cmd[0]=="print":
        pripre=[]
        priin=[]
        preorder(root)
        inorder(root)
        print(' '+' '.join(priin))
        print(' '+' '.join(pripre))
    elif cmd[0]=="find":
        key=int(cmd[1])
        z=node(key)
        if find(root,z):
            print('yes')
        else:
            print('no')
    elif cmd[0]=='delete':
        Min=[]
        key=int(cmd[1])
        z=node(key)
        delete(root,z,0)
    else:
        key=int(cmd[1])
        z=node(key)
        root=insert(root,z)