Rabbit House

class Node:
    value=0
    lchild=None
    rchild=None
    p=None 
    def __init__(self):
        value=0
        lchild=None
        rchild=None
        p=None  
    def visit(self):
        print self.value

def TreeSearch(root,k):
    if root==None or k==root.value:
        return root 
    if k<root.value:
        return TreeSearch(root.lchild, k)
    else:
        return TreeSearch(root.rchild, k)

def IterativeTreeSearch(root,k):
    while root!=None and k!=root.value:
        if k<root.value:
            root=root.lchild 
        else:
            root=root.rchild 
    return root 

def PreOrder(root):
    if root:
        PreOrder(root.lchild)
        print root.value 
        PreOrder(root.rchild)

def TreeMin(root):
    while root.lchild!=None:
        root=root.lchild 
    return root 

def TreeMax(root):
    while root.rchild!=None:
        root=root.rchild
    return root 

def TreeSuccessor(root):
    if root.rchild!=None:
        return TreeMin(root.rchild)
    y=root.p
    while (y!=None and root==y.right):
        root=y 
        y=y.p
    return y 

def TreeInsert(root,z):
    y=None 
    while root!=None:
        y=root 
        if root.value>z.value:
            root=root.lchild 
        else:
            root=root.rchild 
    z.p=y 
    if y==None:
        root=z 
    else:
        if z.value<y.value:
            y.lchild=z 
        else:
            y.rchild=z 

def Transplant(root,u,v):
    if u.p==None:
        root=v 
    else:
        if u==u.p.lchild:
            u.p.lchild=v 
        else:
            u.p.lchild=v
    if v!=None:
        v.p=u.p 
    v.lchild=u.lchild 
    v.rchild=u.rchild 
    if u.lchild!=None:
        u.lchild.p=v 
    if u.rchild!=None:
        u.rchild.p=v

A=Node()
B=Node()
C=Node()
D=Node()
E=Node()
F=Node()
A.value=6
B.value=5
C.value=2
D.value=5
E.value=7
F.value=8
A.lchild=B 
B.lchild=C 
B.rchild=D 
A.rchild=E 
E.rchild=F 
B.p=A 
C.p=B 
D.p=B 
E.p=A 
F.p=E 
print TreeSearch(A, 7)
print IterativeTreeSearch(A, 7)
print TreeSuccessor(A)
G=Node()
G.value=10
TreeInsert(A, G)
PreOrder(A)

Binary Tree