Deletion in Binary Search Tree in DSA Python

Program 1

# Implementation of Binary Search Tree
import os
class Node:
    def __init__(self):
        self.ladd=None
        self.data=None
        self.radd=None

class Tree:
    def __init__(self):
        self.root=None
        #Create Method
    def createTree(self,r,new1):
        if(new1.data<r.data):
            if(r.ladd==None):
                r.ladd=new1
            else:
                self.createTree(r.ladd,new1)  # Recursion
        if(new1.data>r.data):
            if(r.radd==None):
                r.radd=new1
            else:
                self.createTree(r.radd,new1)  # Recursion    

        if(new1.data==r.data):
            print("duplicate element not allowed .")        

     #Inorder Method           
    def inorder(self,p):
        if(p!=None):
            self.inorder(p.ladd)   # left
            print(p.data,end="  ")  # Node
            self.inorder(p.radd)  #right
    #Preorder Method           
    def preorder(self,p):
          if(p!=None):
              print(p.data,end="  ")  # Node
              self.preorder(p.ladd)  # left
              self.preorder(p.radd)  # right
              
   #Postrder Method           
    def postorder(self,p):
        if(p!=None):
            self.postorder(p.ladd)  # left
            self.postorder(p.radd)  # right 
            print(p.data,end="  ")  # Node

# Search Data method

    def searchData(self,pt,s):          
        if(pt==None):
            print("\nElement not found")
        else:
            if(s<pt.data):
                self.searchData(pt.ladd,s) # Recursion
            elif(s>pt.data):
                self.searchData(pt.radd,s) # Resursion
            elif(s==pt.data):   
                print("Searching Success")
    
    # Delete Node Method
    def deleteNode(self,p):
        pt=p
        n=int(input("Enter an element for Delete"))
         #Pointer set to node which we want to delete and prev set to previous node
        while(n!=pt.data):
            prev=pt
            if(n<pt.data):
                    pt=pt.ladd
            else:
                   pt=pt.radd        

        #Node which having left and right address NULL
        if(pt.ladd==None and pt.radd==None):
                if(n<prev.data):                 
                  prev.ladd=None
                else:
                 prev.radd=None    
        else:
            #Node which having left  address is None and right address is not  None
            if(pt.ladd==None and pt.radd!=None):
                if(n<prev.data):
                    prev.ladd=pt.radd
                else:
                    prev.radd=pt.radd
            #Node which having left  address is  not None and right address is   None        
            elif(pt.ladd!=None and pt.radd==None):
                  if(n<prev.data):
                      prev.ladd=pt.ladd
                  else:
                      prev.radd=pt.ladd    

             #Node which having left  address is  not None and right address is Nont  None        
            elif(pt.ladd!=None and pt.radd!=None):
                 temp=pt.ladd

                 while(temp.radd!=None):
                     temp=temp.radd

                 temp.radd=pt.radd
                 if(n<prev.data):
                     prev.ladd=pt.ladd
                 else:
                     prev.radd=pt.ladd         

        print("Delete Node is : ",pt.data)
        pt.ladd=None
        pt.radd=None
        pt=None 

#Main Menu
T=Tree()
os.system('cls')
while(1):
    print("\n-----------------Tree Menu------------------")
    print("                 1.Create Tree ")
    print("                 2.Inorder ")
    print("                 3.Preorder ")
    print("                 4.Postorder ")
    print("                 5.Search")
    print("                 6.Sorting")
    print("                 7.Delete")
    print("                 8.Exit ")
    print("----------------------------------------------")
    choice=int(input("Enter your choice"))
    
    if(choice==1):
       ch="y"
       while(ch=="Y" or ch=="y"):
           n=int(input("Enter an element"))
           new1=Node()
           new1.ladd=None
           new1.data=n
           new1.radd=None
           if(T.root==None):
              T.root=new1
           else:
              T.createTree(T.root,new1)
           ch=input("Want to continue: ")
    elif(choice==2):
        print("Inorder Elements: ")
        T.inorder(T.root)    
    elif(choice==3):
        print("Preorder Elements: ")
        T.preorder(T.root)        
    elif(choice==4):
        print("Postorder Elements: ")
        T.postorder(T.root)
    elif(choice==5):
        s=int(input("Enter an element for search"))
        T.searchData(T.root,s)                            
    elif(choice==6):
               print("Sorted elements")    
               T.inorder(T.root)   
    elif(choice==7):
               T.deleteNode(T.root)              
    else:
        break