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.

Solution (Python):

import sys


class Node(object):
    __slots__ = ["value", "left", "right"]

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


class BinTree(object):
    def __init__(self):
        self._tree = None

    def insert(self, value):
        parent = None
        current = self._tree

        while current is not None:
            parent = current
            if value < current.value:
                current = current.left
            else:
                current = current.right

        if parent is None:
            self._tree = Node(value)
        elif value < parent.value:
            parent.left = Node(value)
        else:
            parent.right = Node(value)

    def find(self, value):
        current = self._tree

        while current is not None:
            if value == current.value:
                return True
            elif value < current.value:
                current = current.left
            else:
                current = current.right

        return False

    def delete(self, value):
        parent = None
        current = self._tree

        while current.value != value:
            parent = current
            if current is None:
                return
            elif value < current.value:
                current = current.left
            else:
                current = current.right

        if current.left is None and current.right is None:
            if parent.left is current:
                parent.left = None
            else:
                parent.right = None
        elif current.left is None:
            if parent.left is current:
                parent.left = current.right
            else:
                parent.right = current.right
        elif current.right is None:
            if parent.left is current:
                parent.left = current.left
            else:
                parent.right = current.left
        else:
            next_node_parent = current
            next_node = current.right
            while next_node.left is not None:
                next_node_parent = next_node
                next_node = next_node.left

            if next_node.right is None:
                if next_node_parent.left is next_node:
                    next_node_parent.left = None
                else:
                    next_node_parent.right = None
            else:
                if next_node_parent.left is next_node:
                    next_node_parent.left = next_node.right
                else:
                    next_node_parent.right = next_node.right

            current.value = next_node.value

    def preoder_walk(self):
        def preoder(node):
            result = []
            if node is None:
                pass
            else:
                result.append(node.value)
                result.extend(preoder(node.left))
                result.extend(preoder(node.right))
            return result

        return preoder(self._tree)

    def inorder_walk(self):
        def inorder(node):
            result = []
            if node is None:
                pass
            else:
                result.extend(inorder(node.left))
                result.append(node.value)
                result.extend(inorder(node.right))
            return result

        return inorder(self._tree)


def print_tree(tree):
    print(" " + " ".join([str(val) for val in tree.inorder_walk()]))
    print(" " + " ".join([str(val) for val in tree.preoder_walk()]))


def print_yes_no(boolean):
    if boolean:
        print("yes")
    else:
        print("no")


def main(commands):
    tree = BinTree()
    for com in commands:
        if com[0] == "insert":
            tree.insert(int(com[1]))
        elif com[0] == "print":
            print_tree(tree)
        elif com[0] == "find":
            print_yes_no(tree.find(int(com[1])))
        elif com[0] == "delete":
            tree.delete(int(com[1]))
        else:
            raise ValueError


if __name__ == "__main__":
    n = int(input())
    commands = [com.split() for com in sys.stdin.readlines()]
    main(commands)

Solution (Python):


class Node(object):

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

        self.key = key


class Tree(object):

    def __init__(self):
        self.root = None

    def insert(self, new_key):
        x = self.root
        y = None

        while x is not None:
            y = x

            if new_key < y.key:
                x = y.left
            else:
                x = y.right

        new_node = Node(new_key)
        new_node.parent = y
        if y is None:
            self.root = new_node
        elif new_key < y.key:
            y.left = new_node
        else:
            y.right = new_node

    def inorder(self, now):
        visited = list()
        if now is None:
            return visited

        visited.extend(self.inorder(now.left))
        visited.append(now.key)
        visited.extend(self.inorder(now.right))
        return visited

    def preorder(self, now):
        visited = list()
        if now is None:
            return visited

        visited.append(now.key)
        visited.extend(self.preorder(now.left))
        visited.extend(self.preorder(now.right))
        return visited

    def order_print(self):
        keys = list()
        keys.append(self.inorder(self.root))
        keys.append(self.preorder(self.root))

        for visited_keys in keys:
            print "",
            print " ".join(map(str, visited_keys))

    def find(self, key):
        """
        keys = self.inorder(self.root)
        if key in keys:
            print "yes"
        else:
            print "no"
        """
        x = self.root
        y = None

        while not (x is None or x.key == key):
            y = x
            if key < y.key:
                x = y.left
            else:
                x = y.right

        if x is not None:
            print "yes"
        else:
            print "no"


    def min_node(self, now):
        """min_node
        Return the node with the minimum key,
        treeting now as the root of a sub tree.
        """
        x = now
        while x.left is not None:
            x = x.left

        return x
        """
        if now.left is not None:
            print "now: {}, left: {}".format(now.key, now.left.key)
            return self.min_node(now.left)
        print "now: {}, left: {}, right: {}".format(now.key, now.left, now.right)
        return now
        """


    def delete(self, key):
        x = self.root
        y = None

        while not(x is None or x.key == key):
            y = x
            if key < y.key:
                x = y.left
            else:
                x = y.right

        
        if x.left is None and x.right is None:
            if y.left == x:
                y.left = None
            else:
                y.right = None
        elif x.left is None or x.right is None:
            child = x.left if x.left is not None else x.right
            child.parent = y
            if y.left == x:
                y.left = child
            else:
                y.right = child
        else:
            next_node = self.min_node(x.right)
            tmp = next_node.key
            self.delete(next_node.key)
            x.key = next_node.key


def main():
    tree = Tree()

    num_orders = int(raw_input())
    for _ in xrange(num_orders):
        order = raw_input()
        if order[0] == 'i':
            new_key = int(order.split()[1])
            tree.insert(new_key)
        elif order[0] == 'p':
            tree.order_print()
        elif order[0] == 'f':
            key = int(order.split()[1])
            tree.find(key)
        elif order[0] == 'd':
            key = int(order.split()[1])
            tree.delete(key)


if __name__ == "__main__":
    main()

Solution (Python):



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


class BinarySearchTree(list):
    def __init__(self):
        list.__init__(self)
        self.root = None

    def insert(self, z):
        z = Node(z)
        y = None
        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 preorder(self):
        def preParse(u):
            if u == None:
                return
            print(" " + str(u.key), end="")
            preParse(u.left)
            preParse(u.right)
        preParse(self.root)
        print("")

    def inorder(self):
        def inParse(u):
            if u == None:
                return
            inParse(u.left)
            print(" " + str(u.key), end="")
            inParse(u.right)
        inParse(self.root)
        print("")

    def print(self):
        self.inorder()
        self.preorder()

    def find(self, k):
        x = self.root
        while x is not None and k != x.key:
            if k < x.key:
                x = x.left
            else:
                x = x.right
        return x

    def delete(self, z):
        
        if z.left is None or z.right is None:
            y = z
        else:
            y = self.getSuccessor(z)
        
        if y.left is not None:
            x = y.left
        else:
            x = y.right
        
        if x is not None:
            x.parent = y.parent

        if y.parent is None:
            self.root = x
        elif y == y.parent.left:
            y.parent.left = x
        else:
            y.parent.right = x
        
        if y != z:
            z.key = y.key

        

    def getSuccessor(self, x):
        if x.right is not None:
            return self.getMinimum(x.right)

        y = x.parent
        while y is not None and x == y.right:
            x = y
            y = y.parent
        return y

    def getMinimum(self, x):
        while x.left is not None:
            x = x.left
        return x


if __name__ == '__main__':

    n = int(input())
    command = [input().split(" ") for _ in range(n)]
    T = BinarySearchTree()

    for c in command:
        if c[0] == "insert":
            T.insert(int(c[1]))
        elif c[0] == "find":
            z = T.find(int(c[1]))
            if z is None:
                print("no")
            else:
                print("yes")
        elif c[0] == "delete":
            z = T.find(int(c[1]))
            T.delete(z)
        else:
            T.print()

Solution (Python):
LEFT = 0
RIGHT = 1

class Node:

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

class BTree:

    def __init__(self):
        self.root = None

    def insert(self, z):
        y = None
        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):
        current = self.root
        while current is not None:
            if current.key == key:
                print("yes")
                return

            if key < current.key:
                current = current.left
            else:
                current = current.right

        print("no")
        return

    def find_successor(self, node):
        current = node.right

        while current.left is not None:
            current = current.left

        return current

    def delete(self, key):
        current = self.root
        parent = None
        parent_lr = None
        while current.key != key:
            if key < current.key:
                parent = current
                parent_lr = LEFT
                current = current.left
            else:
                parent = current
                parent_lr = RIGHT
                current = current.right

            if current is None:
                return None

        if current.left is None and current.right is None:
            if parent_lr == LEFT:
                parent.left = None
            else:
                parent.right = None

        elif current.left is None and current.right is not None:
            if parent_lr == LEFT:
                parent.left = current.right
            else:
                parent.right = current.right

        elif current.left is not None and current.right is None:
            if parent_lr == LEFT:
                parent.left = current.left
            else:
                parent.right = current.left

        else:
            successor = self.find_successor(current)
            new_key = successor.key
            self.delete(successor.key)
            current.key = new_key

        del current


    def print_inorder(self):

        def print_inorder_innner(root):
            if root.left is not None:
                print_inorder_innner(root.left)
            print(" {0}".format(root.key), end="")
            if root.right is not None:
                print_inorder_innner(root.right)

        print_inorder_innner(self.root)
        print("")

    def print_preorder(self):

        def print_preorder_innner(root):
            print(" {0}".format(root.key), end="")

            if root.left is not None:
                print_preorder_innner(root.left)
            if root.right is not None:
                print_preorder_innner(root.right)

        print_preorder_innner(self.root)
        print("")

    def debug_print(self):

        def debug_print_inner(root):
            if root.left is None:
                lstr = "None"
            else:
                lstr = "{0:4d}".format(root.left.key)

            if root.right is None:
                rstr = "None"
            else:
                rstr = "{0:4d}".format(root.right.key)

            print("{0:4d} : {1} , {2}".format(root.key, lstr, rstr))

            if root.left is not None:
                debug_print_inner(root.left)

            if root.right is not None:
                debug_print_inner(root.right)

        root = self.root
        debug_print_inner(root)


if __name__ == '__main__':
    btree = BTree()

    n = int(input())
    inst = []
    for _ in range(n):
        al = input().split()
        if al[0] == "print":
            inst.append(("print", 0))
        elif al[0] == "debug":
            inst.append(("debug", 0))
        else:
            inst.append((al[0], int(al[1])))

    for (i, k) in inst:

        if i == "insert":
            btree.insert(Node(k))
        elif i == "find":
            btree.find(k)
        elif i == "delete":
            btree.delete(k)
        elif i == "debug":
            btree.debug_print()
        else:
            btree.print_inorder()
            btree.print_preorder()

Solution (Python):
import sys
readline = sys.stdin.readline
from copy import deepcopy, copy
class Node:
    __slots__ = ['value', 'left', 'right']
    def __init__(self, value=None):
        self.value = value
        self.left = None
        self.right = None
class BinTree:
    __slots__ = ['_tree', 'result']
    def __init__(self):
        self._tree = None
    def insert(self, value):
        p = None
        c = self._tree
        while c is not None:
            p = c
            if value < c.value:
                c = c.left
            else:
                c = c.right
        if p is None:
            self._tree = Node(value)
        elif value < p.value:
            p.left = Node(value)
        else:
            p.right = Node(value)
    def find(self, value):
        c = self._tree
        while c is not None:
            if value == c.value:
                return True
            elif value < c.value:
                c = c.left
            else:
                c = c.right
        return False
    def delete(self, value):
        parent = None
        current = self._tree
        while current.value != value:
            parent = current
            if current is None:
                return
            elif value < current.value:
                current = current.left
            else:
                current = current.right
        if current.left is None and current.right is None:
            if parent.left is current:
                parent.left = None
            else:
                parent.right = None
        elif current.left is None:
            if parent.left is current:
                parent.left = current.right
            else:
                parent.right = current.right
        elif current.right is None:
            if parent.left is current:
                parent.left = current.left
            else:
                parent.right = current.left
        else:
            next_node_parent = current
            next_node = current.right
            while next_node.left is not None:
                next_node_parent = next_node
                next_node = next_node.left
            if next_node.right is None:
                if next_node_parent.left is next_node:
                    next_node_parent.left = None
                else:
                    next_node_parent.right = None
            else:
                if next_node_parent.left is next_node:
                    next_node_parent.left = next_node.right
                else:
                    next_node_parent.right = next_node.right
            current.value = next_node.value
    def preoder_walk(self):
        self.result = []
        def preoder(node):
            if node is not None:
                self.result.append(node.value)
                preoder(node.left)
                preoder(node.right)
        preoder(self._tree)
        print(" " + " ".join(map(str, self.result)))
    def inorder_walk(self):
        self.result = []
        def inorder(node):
            if node is not None:
                inorder(node.left)
                self.result.append(node.value)
                inorder(node.right)
        inorder(self._tree)
        print(" " + " ".join(map(str, self.result)))
n = int(input())
tree = BinTree()
for _ in range(n):
    com = readline().split()
    if com[0] == "insert":
        tree.insert(int(com[1]))
    elif com[0] == "find":
        print("yes" if tree.find(int(com[1])) else "no")
    elif com[0] == "delete":
        tree.delete(int(com[1]))
    else:
        tree.inorder_walk()
        tree.preoder_walk()

Solution (Python):
import sys
readline = sys.stdin.readline
class Node:
    __slots__ = ['value', 'left', 'right']
    def __init__(self, value=None):
        self.value = value
        self.left = None
        self.right = None
class BinTree:
    __slots__ = ['_tree', 'result']
    def __init__(self):
        self._tree = None
    def insert(self, value):
        p = None
        c = self._tree
        while c is not None:
            p = c
            if value < c.value:
                c = c.left
            else:
                c = c.right
        if p is None:
            self._tree = Node(value)
        elif value < p.value:
            p.left = Node(value)
        else:
            p.right = Node(value)
    def find(self, value):
        c = self._tree
        while c is not None:
            if value == c.value:
                return True
            elif value < c.value:
                c = c.left
            else:
                c = c.right
        return False
    def delete(self, value):
        p = None
        c = self._tree
        while c.value != value:
            p = c
            if c is None:
                return
            if value < c.value:
                c = c.left
            else:
                c = c.right
        if c.left is None:
            if p.left == c:
                p.left = c.right
            else:
                p.right = c.right
        elif c.right is None:
            if p.left == c:
                p.left = c.left
            else:
                p.right = c.left
        elif c.right.left is None:
            c.right.left = c.left
            if p.left == c:
                p.left = c.right
            else:
                p.right = c.right
        else:
            q = c.right
            while q.left.left is not None:
                q = q.left
            c.value = q.left.value
            q.left = q.left.right
        return
    def preoder_walk(self):
        self.result = []
        def preoder(node):
            if node is not None:
                self.result.append(node.value)
                preoder(node.left)
                preoder(node.right)
        preoder(self._tree)
        print(" " + " ".join(map(str, self.result)))
    def inorder_walk(self):
        self.result = []
        def inorder(node):
            if node is not None:
                inorder(node.left)
                self.result.append(node.value)
                inorder(node.right)
        inorder(self._tree)
        print(" " + " ".join(map(str, self.result)))
n = int(input())
tree = BinTree()
for _ in range(n):
    com = readline().split()
    if com[0] == "insert":
        tree.insert(int(com[1]))
    elif com[0] == "find":
        print("yes" if tree.find(int(com[1])) else "no")
    elif com[0] == "delete":
        tree.delete(int(com[1]))
    else:
        tree.inorder_walk()
        tree.preoder_walk()

Solution (Python):
import sys
readline = sys.stdin.readline
class Node:
    __slots__ = ['value', 'left', 'right']
    def __init__(self, value = None, left = None, right = None):
        self.value = value
        self.left = left
        self.right = right
class BinTree:
    __slots__ = ['_tree', 'result']
    def __init__(self):
        self._tree = None
    def insert(self, value):
        p = None
        c = self._tree
        while c is not None:
            p = c
            if value < c.value:
                c = c.left
            else:
                c = c.right
        if p is None:
            self._tree = Node(value)
        elif value < p.value:
            p.left = Node(value)
        else:
            p.right = Node(value)
    def find(self, value):
        c = self._tree
        while c is not None:
            if value == c.value:
                return True
            elif value < c.value:
                c = c.left
            else:
                c = c.right
        return False
    def delete(self, value):
        def node_move(p, c, a):
            if p.left == c:
                p.left = a
            else:
                p.right = a
        p = None
        c = self._tree
        while c.value != value:
            p = c
            if c is None:
                return
            if value < c.value:
                c = c.left
            else:
                c = c.right
        if c.left is None:
            node_move(p, c, c.right)
        elif c.right is None:
            node_move(p, c, c.left)
        elif c.right.left is None:
            c.right.left = c.left
            node_move(p, c, c.right)
        else:
            q = c.right
            while q.left.left is not None:
                q = q.left
            c.value = q.left.value
            q.left = q.left.right
        return
    def preoder_walk(self):
        self.result = []
        def preoder(node):
            if node is not None:
                self.result.append(node.value)
                preoder(node.left)
                preoder(node.right)
        preoder(self._tree)
        print(" " + " ".join(map(str, self.result)))
    def inorder_walk(self):
        self.result = []
        def inorder(node):
            if node is not None:
                inorder(node.left)
                self.result.append(node.value)
                inorder(node.right)
        inorder(self._tree)
        print(" " + " ".join(map(str, self.result)))
n = int(input())
tree = BinTree()
for _ in range(n):
    com = readline().split()
    if com[0] == "insert":
        tree.insert(int(com[1]))
    elif com[0] == "find":
        print("yes" if tree.find(int(com[1])) else "no")
    elif com[0] == "delete":
        tree.delete(int(com[1]))
    else:
        tree.inorder_walk()
        tree.preoder_walk()

Solution (Python):
import sys
readline = sys.stdin.readline
class Node:
    __slots__ = ['value', 'left', 'right']
    def __init__(self, value = None, left = None, right = None):
        self.value = value
        self.left = left
        self.right = right
class BinTree:
    __slots__ = ['_tree', 'result']
    def __init__(self):
        self._tree = None
    def insert(self, value):
        p = None
        c = self._tree
        while c is not None:
            p = c
            if value < c.value:
                c = c.left
            else:
                c = c.right
        if p is None:
            self._tree = Node(value)
        elif value < p.value:
            p.left = Node(value)
        else:
            p.right = Node(value)
    def find(self, value):
        c = self._tree
        while c is not None:
            if value == c.value:
                return True
            elif value < c.value:
                c = c.left
            else:
                c = c.right
        return False
    def delete(self, value):
        def node_move(p, c, a):
            if p.left == c:
                p.left = a
            else:
                p.right = a
        c = self._tree
        p = Node(None, c)
        while c.value != value:
            p = c
            if c is None:
                return
            if value < c.value:
                c = c.left
            else:
                c = c.right
        if c.left is None:
            node_move(p, c, c.right)
        elif c.right is None:
            node_move(p, c, c.left)
        elif c.right.left is None:
            c.right.left = c.left
            node_move(p, c, c.right)
        else:
            q = c.right
            while q.left.left is not None:
                q = q.left
            c.value = q.left.value
            q.left = q.left.right
        return
    def preoder_walk(self):
        self.result = []
        def preoder(node):
            if node is not None:
                self.result.append(node.value)
                preoder(node.left)
                preoder(node.right)
        preoder(self._tree)
        print(" " + " ".join(map(str, self.result)))
    def inorder_walk(self):
        self.result = []
        def inorder(node):
            if node is not None:
                inorder(node.left)
                self.result.append(node.value)
                inorder(node.right)
        inorder(self._tree)
        print(" " + " ".join(map(str, self.result)))
n = int(input())
tree = BinTree()
for _ in range(n):
    com = readline().split()
    if com[0] == "insert":
        tree.insert(int(com[1]))
    elif com[0] == "find":
        print("yes" if tree.find(int(com[1])) else "no")
    elif com[0] == "delete":
        tree.delete(int(com[1]))
    else:
        tree.inorder_walk()
        tree.preoder_walk()