In [ ]:
def insert(x,nums):
    if nums == []:
        return [x]
    elif x <= nums[0]:
        return [x] + nums
    else:
        return [nums[0]] + insert(x,nums[1:])
    
def isort(nums):
    if nums == []:
        return []
    else:  
        return insert(nums[0],isort(nums[1:]))
In [1]:
# implementing sets; so no duplicates
class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
    
    def find_min(self):
        if self.left is None:
            return self.value
        else:
            return self.left.find_min()
        
    # insert returns True or False depending on whether the value was inserted
    def insert(self, x):
        if x < self.value:
            if self.left is None:
                n = Node(x)
                self.left = n
                return True
            else:
                return self.left.insert(x)
        elif x > self.value:
            if self.right is None:
                n = Node(x)
                self.right = n
                return True
            else:
                return self.right.insert(x)
        else:
            return False
    
    def delete(self,x):
        return self.delete_helper(x) is not None
    
    def delete_helper(self,x):
        if self.value == x: # found the value to delete
            if self.left is None:
                return self.right
            elif self.right is None:
                return self.left
            else:
                # find the smallest value in the right subtree
                # and replace the current value with that value
                # then delete that value from the right subtree
                min_right = self.right.find_min()
                self.value = min_right
                self.right = self.right.delete_helper(min_right)
                return self
        elif x < self.value:
            if self.left is None:
                return None
            else:
                self.left = self.left.delete_helper(x)
                return self
        else:
            if self.right is None:
                return None
            else:
                self.right = self.right.delete_helper(x)
                return self

    def __str__(self):
        if self.left is None and self.right is None:
            return str(self.value)
        elif self.left is None:
            return str(self.value) + "," + str(self.right)
        elif self.right is None:
            return str(self.left) + "," + str(self.value)
        else:
            return str(self.left) + "," + str(self.value)  + "," + str(self.right)
    

    # 10,20,30,40,50,60,70,80,90,100
In [2]:
class BST:
    def __init__(self):
        self.root = None
    
    def insert(self, x):
        if self.root is None:
            self.root = Node(x)
            return True
        else:
            return self.root.insert(x)

    def delete(self,x):
        if self.root is None:
            return False
        else:
            return self.root.delete(x)

    def __str__(self):
        return str(self.root)
In [4]:
t = BST()
t.insert(40)
t.insert(50)
t.insert(30)
t.insert(10)
t.insert(8)
print(t)
8,10,30,40,50
In [5]:
t.delete(30)
print(t)
8,10,40,50
In [1]:
str(None)
Out[1]:
'None'