In [4]:

    

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


    

In [33]:

    

def inOrderTreeWalk(x):
    if x is not None:
        inOrderTreeWalk(x.left)
        print(x.data, end='')
        inOrderTreeWalk(x.right)


    

In [10]:

    

def treeSearch(x, k):
    if x is None or x.data == k.data:
        return x
    elif k.data <= x.data:
        return treeSearch(x.left, k)
    return treeSearch(x.right, k)


    

In [19]:

    

def iterativeTreeSearch(x, k):
    while x is not None and x.data != k.data:
        if k.data <= x.data:
            x = x.left
        else:
            x = x.right
    return x


    

In [27]:

    

def minimum(x):
    while x.left is not None:
        x = x.left
    return x


    

In [29]:

    

def maximum(x):
    while x.right is not None:
        x = x.right
    return x


    

In [36]:

    

def successor(x):
    if x.right is not None:
        return minimum(x.right)
    y = x.parent
    while y is not None and x == y.right:
        x = y
        y = y.parent
    return y


    

In [40]:

    

def predecessor(x):
    if x.left is not None:
        return maximum(x.left)
    y = x.parent
    while y is not None and x == y.left:
        x = y
        y = y.parent
    return y


    

In [50]:

    

def insert(x, z):
    y = None
    while x is not None:
        y = x
        if z.data < x.data:
            x = x.left
        else:
            x = x.right
    z.parent = y
    if y is None:
        x = z # Tree was empty
    elif z.data < y.data:
        y.left = z
    else:
        y.right = z


    

In [ ]:

    

def delete


    

In [ ]:

    

root = Node(5)

root.left = Node(3, root)
root.left.right = Node(4, root.left)
root.left.left = Node(2, root.left)

root.left.left.left = Node(1, root.left.left)

root.right = Node(8, root)
root.right.right = Node(9, root.right)
root.right.left = Node(7, root.right)
root.right.left.left = Node(6, root.right.left)


    

In [51]:

    

root = Node(5)
insert(root, Node(3))
insert(root, Node(4))
insert(root, Node(2))
insert(root, Node(1))
insert(root, Node(8))
insert(root, Node(9))
insert(root, Node(7))
insert(root, Node(6))


    

In [52]:

    

print("Tree in order:", end=' ')
inOrderTreeWalk(root)
print()

print("Find 7: ", treeSearch(root, Node(7)).data, sep='')
print("Find 2: ", iterativeTreeSearch(root, Node(2)).data, sep='')
print("Minimum: ", minimum(root).data, sep='')
print("Maximum: ", maximum(root).data, sep='')
for i in range(1,9):
    print("Successor(",i,"): ", successor(iterativeTreeSearch(root, Node(i))).data, sep='')
for i in range(2,10):
    print("Predecessor(",i,"): ", predecessor(iterativeTreeSearch(root, Node(i))).data, sep='')


    

    




Tree in order: 123456789
Find 7: 7
Find 2: 2
Minimum: 1
Maximum: 9
Successor(1): 2
Successor(2): 3
Successor(3): 4
Successor(4): 5
Successor(5): 6
Successor(6): 7
Successor(7): 8
Successor(8): 9
Predecessor(2): 1
Predecessor(3): 2
Predecessor(4): 3
Predecessor(5): 4
Predecessor(6): 5
Predecessor(7): 6
Predecessor(8): 7
Predecessor(9): 8

In [ ]: