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:
class Node():
	def __init__(self, key):
		self.parent = None
		self.left = None
		self.right = None
		self.key = key
 
class Tree():
	def __init__(self):
		self.root = None
	def insert_node(self, key):
		z = Node(key)
		y = None
		x = self.root
		while x:
			y = x
			if z.key < x.key:
				x = x.left
			else:
				x = x.right
		z.parent = y
		if y == None:
			self.root = z;
		elif z.key < y.key:
			y.left = z
		else:
			y.right = z
	def delete_node(self, key):
		node = self.find_node(key)
		if node.left and node.right:
			right_min = node.right
			while right_min.left:
				right_min = right_min.left
			node.key = right_min.key
			node = right_min
		if node.left or node.right:
			child = node.left if node.left else node.right
			if node.parent.left == node:
				node.parent.left = child
				child.parent = node.parent
			else:
				node.parent.right = child
				child.parent = node.parent
		else:
			if node.parent.left == node:
				node.parent.left = None
			else:
				node.parent.right = None

	def pre_order(self, node):
		print(" {}".format(node.key), end = "")
		if node.left:
			self.pre_order(node.left)
		if node.right:
			self.pre_order(node.right)
	def in_order(self, node):
		if node.left:
			self.in_order(node.left)
		print(" {}".format(node.key), end = "")
		if node.right:
			self.in_order(node.right)
	def print_node(self):
		self.in_order(self.root)
		print("")
		self.pre_order(self.root)
		print("")
	def find_node(self, key):
		node = self.root;
		while node:
			if node.key == key:
				return node
			elif node.key > key:
				node = node.left
			else:
				node = node.right
		return None

tree = Tree()
n = int(input())
for i in range(n):
	c = input().split()
	if c[0] == "insert":
		tree.insert_node(int(c[1]))
	elif c[0] == "find":
		print("yes" if tree.find_node(int(c[1])) else "no")
	elif c[0] == "delete":
		tree.delete_node(int(c[1]))
	else:
		tree.print_node()

Submission status: Accepted

Solution code:
import sys
import time

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

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

def find(node, key):
    if node is None:
        return False
    elif node.key == key:
        return True
    elif node.key > key:
        return find(node.left, key)
    else:
        return find(node.right, key)

def delete(node, key):
    if node is not None:
        if node.key == key:
            reconstTree(node)
        elif node.key > key:
            delete(node.left, key)
        else:
            delete(node.right, key)

def reconstTree(node):
    if node.left is None and node.right is None:
        #print "-----leaf-----"
        #print node.key
        if node.parent.left == node:
            node.parent.left = None
        else:
            node.parent.right = None
    elif node.left is not None and node.right is not None:
        #print "-----both-----"
        #print node.key
        sib = node.right
        while sib.left is not None:
            sib = sib.left
        node.key = sib.key
        reconstTree(sib)
    elif node.left is not None:
        #print "-----left-----"
        #print node.key
        if node.parent.left == node:
            node.parent.left = node.left
        else:
            node.parent.right = node.left
        node.left.parent = node.parent
    else:
        #print "-----right-----"
        #print node.key
        if node.parent.left == node:
            node.parent.left = node.right
        else:
            node.parent.right = node.right
        node.right.parent = node.parent

def inorderTreeWalk(node):
    global In
    if node:
        inorderTreeWalk(node.left)
        In.append(str(node.key))
        inorderTreeWalk(node.right)

def preorderTreeWalk(node):
    global Pre
    if node:
        Pre.append(str(node.key))
        preorderTreeWalk(node.left)
        preorderTreeWalk(node.right)

if __name__ == "__main__":
    lines = sys.stdin.readlines()
    del lines[0]

    root = None
    for line in lines:
        if line[0] == "p":
            In = []
            Pre = []
            inorderTreeWalk(root)
            print " " + " ".join(map(str, In))
            preorderTreeWalk(root)
            print " " + " ".join(map(str, Pre))
        else:
            com = line.split()
            if com[0][0] == "i":
                insert(Node(int(com[1])))
            elif com[0][0] == "f":
                if find(root, int(com[1])):
                    print "yes"
                else:
                    print "no"
            else:
                delete(root, int(com[1]))

Submission status: Accepted

Solution code:
import sys

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

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

def find(node, key):
    if node is None:
        return False
    elif node.key == key:
        return True
    elif node.key > key:
        return find(node.left, key)
    else:
        return find(node.right, key)

def delete(node, key):
    if node is not None:
        if node.key == key:
            reconstTree(node)
        elif node.key > key:
            delete(node.left, key)
        else:
            delete(node.right, key)

def reconstTree(node):
    if node.left is not None and node.right is not None:
        sib = node.right
        while sib.left is not None:
            sib = sib.left
        node.key = sib.key
        reconstTree(sib)
    else:
        parent = node.parent
        if node.left is not None:
            child = node.left
        elif node.right is not None:
            child = node.right
        else:
            child = None

        if parent.left == node:
            parent.left = child
        else:
            parent.right = child

        if child is not None:
            child.parent = parent

def inorderTreeWalk(node):
    global In
    if node:
        inorderTreeWalk(node.left)
        In.append(str(node.key))
        inorderTreeWalk(node.right)

def preorderTreeWalk(node):
    global Pre
    if node:
        Pre.append(str(node.key))
        preorderTreeWalk(node.left)
        preorderTreeWalk(node.right)

if __name__ == "__main__":
    lines = sys.stdin.readlines()
    del lines[0]

    root = None
    for line in lines:
        if line[0] == "p":
            In = []
            Pre = []
            inorderTreeWalk(root)
            print " " + " ".join(map(str, In))
            preorderTreeWalk(root)
            print " " + " ".join(map(str, Pre))
        else:
            com = line.split()
            if com[0][0] == "i":
                insert(Node(int(com[1])))
            elif com[0][0] == "f":
                if find(root, int(com[1])):
                    print "yes"
                else:
                    print "no"
            else:
                delete(root, int(com[1]))

Submission status: Accepted

Solution code:
import sys
import os

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
        
    def insert_node(self, node):
        if node.value <= self.value:
            if self.left is None:
                self.left = node
            else:
                self.left.insert_node(node)
        else:
            if self.right is None:
                self.right = node
            else:
                self.right.insert_node(node)

    def find_node_by_value(self, value):
        if self.value == value:
            return self
        elif value < self.value:
            if self.left is None:
                return None
            else:
                return self.left.find_node_by_value(value)
        elif value > self.value:
            if self.right is None:
                return None
            else:
                return self.right.find_node_by_value(value)
        else:
            assert(False)   

    def next_node_in_inorder(self):
        if self.right is not None:
            return self.right.smallest_offspring(self)
        else:
            return None

    def smallest_offspring(self, parent):
        if self.left is not None:
            return self.left.smallest_offspring(self)
        else:
            return (self, parent)

    def get_parent_of(self, value, parent_cand=None, is_left_child=None):
        if self.value == value:
            return parent_cand, is_left_child
        else:
            if value < self.value and self.left is not None:
                return self.left.get_parent_of(value, self, True)
            elif value > self.value and self.right is not None:
                return self.right.get_parent_of(value, self, False)
            else:
                assert(False)

    def delete_child(self, node):
        if self.left == node:
            self.left = None
        elif self.right == node:
            self.right = None
        else:
            assert(False)
            
    def delete_node(self, parent, value):
        # recursive
        if value < self.value and self.left is not None:
            self.left.delete_node(self, value)
        elif self.value < value and self.right is not None:
            self.right.delete_node(self, value)
        # delete
        elif self.left is None and self.right is None:
            # no children
            parent.delete_child(self)
        elif self.left is not None and self.right is not None:
            n, p = self.next_node_in_inorder()
            self.value = n.value
            n.delete_node(p, n.value)
        elif self.left is not None:
            self.value = self.left.value
            self.right = self.left.right
            self.left = self.left.left
        elif self.right is not None:
            self.value = self.right.value
            self.left = self.right.left
            self.right = self.right.right
    
#     def delete_node_by_value(self, value):
#         node = self.find_node_by_value(value)
#         parent, node_is_left_child = self.get_parent_of(value)
#         if node.left is None and node.right is None:
#             # hard delete
#             if parent is not None:
#                 if node_is_left_child:
#                     parent.left = None
#                 else:
#                     parent.right = None
#             else:
#                 return 'DELETE_BST'
#         else:
#         self.forcedelete(node, parent, node_is_left_child)

                
    def print_node_by_preorder(self):
        print('', self.value, end='')
        if self.left is not None:
            self.left.print_node_by_preorder()
        if self.right is not None:
            self.right.print_node_by_preorder()


    def print_node_by_inorder(self):
        if self.left is not None:
            self.left.print_node_by_inorder()
        print('', self.value, end='')
        if self.right is not None:
            self.right.print_node_by_inorder()

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

    def cmd_insert(self, k):
        if self.root is None:
            self.root = Node(k)
        else:
            self.root.insert_node(Node(k))

    def cmd_find(self, k):
        if self.root is None:
            return False
        else:
            return (self.root.find_node_by_value(k) is not None)

    def cmd_delete(self, k):
        if self.root is None:
            pass
        else:
            self.root.delete_node(parent=self, value=k)

    def delete_child(self, node):
        assert(self.root == node)
        self.root = None

    def cmd_print(self):
        if self.root is not None:
            self.root.print_node_by_inorder()
            print()
            self.root.print_node_by_preorder()
            print()


if __name__ == '__main__':
    bst = BST()

    lines = []
    for line in sys.stdin:
        lines.append(line.rstrip())
    num_cmds = int(lines[0])
    for line in lines[1:1+num_cmds]:
        line_split = line.split(' ')
        cmd = line_split[0]

        try:
            val = int(line_split[1])
        except:
            pass
        if cmd == 'insert':
            bst.cmd_insert(val)
        elif cmd == 'find':
            if bst.cmd_find(val):
                print('yes')
            else:
                print('no')
        elif cmd == 'print':
            bst.cmd_print()
        elif cmd == 'delete':
            bst.cmd_delete(val)
        else:
            assert(False)

Submission status: Accepted

Solution code:
#coding:utf-8
#1_8_C
class Node:
    def __init__(self, key):
        self.key = key
        self.parent = None
        self.left = None
        self.right = None
class Tree:
    def __init__(self):
        self.root = None

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

    def find(self, node, key):
        if node is None:
            return None

        if key == node.key:
            return node
        elif key < node.key:
            return self.find(node.left, key)
        else:
            return self.find(node.right, key)

    def delete(self, key):
        del_node = self.find(self.root, key)
        if del_node.right and del_node.left:
            # del_node has two children
            right_min = del_node.right
            while right_min.left:
                right_min = right_min.left
            tmp = right_min.key
            self.delete(right_min.key)
            del_node.key = tmp
        elif del_node.right or del_node.left:
            # del_node has only one children
            child = del_node.right if del_node.right else del_node.left
            if del_node.parent.right == del_node:
                del_node.parent.right = child
                child.parent = del_node.parent
            else:
                del_node.parent.left = child
                child.parent = del_node.parent
        else:
            # del_node has no child
            if del_node.parent.right == del_node:
                del_node.parent.right = None
            else:
                del_node.parent.left = None


def inorder(node):
    if node is None:
        return
    inorder(node.left)
    print(" {}".format(node.key), end = "")
    inorder(node.right)

def preorder(node):
    if node is None:
        return
    print(" {}".format(node.key), end = "")
    preorder(node.left)
    preorder(node.right)

def execute(tree, cmd):
    if cmd[0] == 'insert':
        t.insert(Node(int(cmd[1])))
    elif cmd[0] == 'find':
        if tree.find(tree.root, int(cmd[1])):
            print('yes')
        else:
            print('no')
    elif cmd[0] == 'delete':
        tree.delete(int(cmd[1]))
    else:
        inorder(t.root)
        print()
        preorder(t.root)
        print()

m = int(input())
t = Tree()
for i in range(m):
    execute(t, input().split())

Submission status: Accepted

Solution code:
class BinarySearchTree:

    def __init__(self):
        self.root = None

    def insert(self, z):
        p = None
        x = self.root
        while x != None:
            p = x
            if z.key < x.key : x = x.left
            else             : x = x.right
        z.p = p
        if p == None      : self.root = z
        elif z.key < p.key: p.left  = z
        else              : p.right = z

    def get_inorder_list(self):
        def _get_inorder_list(root):
            l = root.left
            r = root.right
            if l: yield from _get_inorder_list(l)
            yield root.key
            if r: yield from _get_inorder_list(r)
        yield from _get_inorder_list(self.root)

    def get_preorder_list(self):
        def _get_preorder_list(root):
            l = root.left
            r = root.right
            yield root.key
            if l: yield from _get_preorder_list(l)
            if r: yield from _get_preorder_list(r)
        yield from _get_preorder_list(self.root)

    def find(self, k):
        z = self.root
        while z:
            if k == z.key: return z
            if k <  z.key: z = z.left
            else         : z = z.right
        return None

    def delete(self, k):
        def ldelete(z):
            def get_next(x):
                c = x.left if x.left else x.right
                if c: return get_next(c)
                else: return x
            if z.left and z.right:
                next_node = get_next(z.right)
                z_key_n = next_node.key
                ldelete(next_node)
                z.key = z_key_n
            else:
                c = z.left if z.left else z.right
                if   z.p == None    : self.root = c
                elif z.key < z.p.key: z.p.left  = c
                else                : z.p.right = c
                if c: c.p = z.p
        z = self.find(k)
        if z: ldelete(z)
# end class BinarySearchTree:

class Node:
    def __init__(self, k):
        self.key = k
        self.p = None
        self.left = None
        self.right = None
#end class Node:
       

if __name__=='__main__':
    m = int(input())

    T = BinarySearchTree()
    for _ in range(m):        
        op = input().split()
        if   op[0] == 'insert': T.insert( Node(int(op[1])) )
        elif op[0] == 'delete': T.delete( int(op[1]) )
        elif op[0] == 'find'  : print("yes" if T.find(int(op[1])) else "no")
        else:
            print("",*T.get_inorder_list())
            print("",*T.get_preorder_list())

Submission status: Accepted

Solution code:
class BinarySearchTree:

    def __init__(self):
        self.root = None

    def insert(self, z):
        p = None
        x = self.root
        while x != None:
            p = x
            if z.key < x.key : x = x.left
            else             : x = x.right
        z.p = p
        if p == None      : self.root = z
        elif z.key < p.key: p.left  = z
        else              : p.right = z

    def get_inorder_list(self):
        def _get_inorder_list(root):
            l = root.left
            r = root.right
            if l: yield from _get_inorder_list(l)
            yield root.key
            if r: yield from _get_inorder_list(r)
        yield from _get_inorder_list(self.root)

    def get_preorder_list(self):
        def _get_preorder_list(root):
            l = root.left
            r = root.right
            yield root.key
            if l: yield from _get_preorder_list(l)
            if r: yield from _get_preorder_list(r)
        yield from _get_preorder_list(self.root)

    def find(self, k):
        z = self.root
        while z:
            if k == z.key: return z
            if k <  z.key: z = z.left
            else         : z = z.right
        return None

    def delete(self, k):
        def ldelete(z):
            if z.left and z.right:
                c = z.right
                while c:
                    next_node = c
                    c = c.left if c.left else c.right
                z_key_n = next_node.key
                ldelete(next_node)
                z.key = z_key_n
            else:
                c = z.left if z.left else z.right
                if   z.p == None    : self.root = c
                elif z.key < z.p.key: z.p.left  = c
                else                : z.p.right = c
                if c: c.p = z.p
        z = self.find(k)
        if z: ldelete(z)
# end class BinarySearchTree:

class Node:
    def __init__(self, k):
        self.key = k
        self.p = None
        self.left = None
        self.right = None
#end class Node:
       

if __name__=='__main__':
    m = int(input())

    T = BinarySearchTree()
    for _ in range(m):        
        op = input().split()
        if   op[0] == 'insert': T.insert( Node(int(op[1])) )
        elif op[0] == 'delete': T.delete( int(op[1]) )
        elif op[0] == 'find'  : print("yes" if T.find(int(op[1])) else "no")
        else:
            print("",*T.get_inorder_list())
            print("",*T.get_preorder_list())

Submission status: Accepted

Solution code:
def insert(r, n):
    if 0 == len(T):
        T[n] = [None, None, None]
    else:
        if n < r:
            left = T[r][0]
            if left == None:
                T[r][0] = n
                T[n] = [None, None, r]
            else:
                insert(left, n)
        if r < n:
            right = T[r][1]
            if right == None:
                T[r][1] = n
                T[n] = [None, None, r]
            else:
                insert(right, n)

def find(n):
    if n in T:
        return True
    else:
        return False

def dele(r, n):
    z = T[n]
    left = z[0]
    right = z[1]
    p = z[2]
    if left is None and right is None:
        i = T[p].index(n)
        T[p][i] = None
        del T[n]
    elif left is None and right is not None:
        x = T[p].index(n)
        T[p][x] = right
        T[right][2] = z[2]
        del T[n]
    elif left is not None and right is None:
        x = T[p].index(n)
        T[p][x] = left
        T[left][2] = z[2]
        del T[n]
    elif left is not None and right is not None:
        inorder = list(map(int, print_inorder(r).split()))
        next_n = inorder[inorder.index(n) + 1]
        if r == n:
            r = next_n
        dele(r, next_n)
        T[next_n] = T[n]
        del T[n]
        n_r = T[next_n][1]
        n_p = T[next_n][2]
        if n_r is not None:
            v = T[n_r]
            if v[0] == n:
                v[0] = next_n
            if v[1] == n:
                v[1] = next_n
            if v[2] == n:
                v[2] = next_n
        if n_p is not None:
            v = T[n_p]
            if v[0] == n:
                v[0] = next_n
            if v[1] == n:
                v[1] = next_n
            if v[2] == n:
                v[2] = next_n
    return r

def print_inorder(r):
    left = T[r][0]
    right = T[r][1]
    ans = ""
    if left != None:
        ans += print_inorder(left)
    ans += " {}".format(r)
    if right != None:
        ans += print_inorder(right)
    return ans

def print_preorder(r):
    left = T[r][0]
    right = T[r][1]
    ans = " {}".format(r)
    if left != None:
        ans += print_preorder(left)
    if right != None:
        ans += print_preorder(right)
    return ans

n = int(input())
T = {}

root = None
for i in range(n):
    inst = input()
    if inst[0] == 'i':
        num = int(inst[7:])
        if i == 0:
            root = num
        insert(root, num)
    elif inst[0] == 'f':
        num = int(inst[5:])
        if find(num):
            print("yes")
        else:
            print("no")
    elif inst[0] == 'd':
        num = int(inst[7:])
        root = dele(root, num)
    elif inst[0] == 'p':
        print(print_inorder(root))
        print(print_preorder(root))

Submission status: Accepted

Solution code:
import sys

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

    def append_child(self, child):
        if self.key > child.key:
            self.left = child
            child.parent = self
        elif self.key < child.key:
            self.right = child
            child.parent = self
        else:
            raise "cannot append a child with same key"

    def remove(self, tree):
        parent = self.parent
        if self.left and self.right:
            child = self.right
            while child.left is not None:
                child = child.left
            child.remove(tree)
            self.key = child.key
        elif self.left or self.right:
            child = self.left or self.right
            if parent is None: # if this is root
                self.root = child
                child.parent = None
            else:
                parent.append_child(child)
        else:
            if parent is None: # if this is root
                tree.root = None
            elif self is parent.left:
                parent.left = None
            else:
                parent.right = None

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

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

        node = self.root
        parent = None
        while node is not None:
            if x > node.key:
                parent = node
                node = node.right
            elif x < node.key:
                parent = node
                node = node.left
            else:
                return node

        parent.append_child(inserted)
        return inserted

    def delete(self, x):
        deleted = self.find(x)
        if deleted is None:
            return False
        deleted.remove(self)
        return True

    def find(self, x):
        node = self.root
        while node is not None:
            if x == node.key:
                return node
            elif x > node.key:
                node = node.right
            else:
                node = node.left
        return None

    def pre_order(self):
        keys = []
        self.do_pre_order(self.root, keys)
        print(' ' + ' '.join(map(str, keys)))

    def do_pre_order(self, node, keys):
        if node is None:
            return
        keys.append(node.key)
        self.do_pre_order(node.left, keys)
        self.do_pre_order(node.right, keys)

    def in_order(self):
        keys = []
        self.do_in_order(self.root, keys)
        print(' ' + ' '.join(map(str, keys)))

    def do_in_order(self, node, keys):
        if node is None:
            return
        self.do_in_order(node.left, keys)
        keys.append(node.key)
        self.do_in_order(node.right, keys)

# main
tree = BinaryTree()
lines = sys.stdin.readlines()

for line in lines[1:]:
    if len(line.rstrip()) == 0:
        continue

    command = line.rstrip().split(' ')

    if command[0] == 'insert':
        tree.insert(int(command[1]))
    elif command[0] == 'print':
        tree.in_order()
        tree.pre_order()
    elif command[0] == 'find':
        if (tree.find(int(command[1]))):
            print('yes')
        else:
            print('no')
    elif command[0] == 'delete':
        tree.delete(int(command[1]))
    else:
        raise 'unknown command: ' + command[0]