How to delete a node in Binary Search Tree using Python

Question

def delete_a_node(self,data):
    if self.root==None:
        print("Empty BST")
    else:
        parent=None
        node=self.root
        replace_node=None
        while(node!=None and node.data!=data):
            parent=node
            if data>=node.data:
                node=node.rightchild
                flag=1
            else:
                node=node.leftchild
                flag=0

        if node is None:
            print("node not in BST.")
        else:
            if (node.leftchild==None) and (node.rightchild==None):
                if (flag):
                    parent.rightchild=None
                else:
                    parent.leftchild=None
                del node
            elif (node.leftchild==None) or (node.rightchild==None):
                if node.leftchild==None:
                    if(flag):
                        parent.rightchild=node.rightchild
                    else:
                        parent.leftchild=node.rightchild
                else  :
                    if(flag):
                        parent.rightchild==node.leftchild
                    else:
                        parent.leftchild=node.leftchild

                del node


            else:
                 replace_node,parent=self.minimum_element(node.rightchild)
                 node=replace_node
                 if parent==None:
                     node.rightchild=None
                 else:
                     parent.leftchild=None
                  del replace_node





def minimum_element(self,node):
    if self.root==None:
        print("Empty BST")
    else:
        parent=None
        while(node.leftchild!=None):
            parent=node
            node=node.leftchild
        return (node,parent)

Hello guys, I was trying to delete a node from binary search tree. I tried to learn it from https://www.geeksforgeeks.org/binary-search-tree-set-2-delete/. Since, they are using recursion in their code. I was unable to grasp it well.

So, I tried to make this code. Here I initialize root in init method and rest two methods are in front of you.

  def __init__(self):
    self.root=None

FLAG Variable: I used it to just find the relationship between the parent node and data node(we want to delete).

As we know, There are three cases

1. When the node we want to delete has no child (it's working fine)
2. When the node we want to delete has one child (it's working fine)
3. When the node we want to delete has both the children(HERE IS THE PROBLEM)

Please, Can anyone help me with this code?

Would you mind showing me,

1. correct method to delete the node from BST
2. should I use del node in python or not, because of I just read that there is no need to free up space in Python.
3. Is my complexity too much comparing to https://www.geeksforgeeks.org/binary-search-tree-set-2-delete/ code?

Output:

bst.inorder() 25--15--10--4--12--22--18--24--50--35--31--44--70--66--55--90--105--120--

bst.delete_a_node(15)

bst.inorder() 25--15--10--4--12--22--18--24--50--35--31--44--70--66--55--90--105--120--

Thank You in Advance :)

Answer 1

    def delete_a_node(self,data):
    if self.root==None:
        print("Empty BST")
    else:
        parent=None
        node=self.root
        replace_node=None
        while(node!=None and node.data!=data):
            parent=node
            if data>=node.data:
                node=node.rightchild
                flag=1
            else:
                node=node.leftchild
                flag=0


        if node is None:
            print("node not in BST.")

        else:


            if (node.leftchild==None) and (node.rightchild==None):
                if (flag):
                    parent.rightchild=None
                else:
                    parent.leftchild=None
                del node

            elif (node.leftchild==None) or (node.rightchild==None):
                if node.leftchild==None:
                    if(flag):
                        parent.rightchild=node.rightchild
                    else:
                        parent.leftchild=node.rightchild
                else  :
                    if(flag):
                        parent.rightchild==node.leftchild
                    else:
                        parent.leftchild=node.leftchild

                del node


            else:
                 replace_node=self.minimum_element(node.rightchild)
                 temp=replace_node.data
                 self.delete_a_node(replace_node.data)
                 node.data=temp

def minimum_element(self,node):
    if self.root==None:
        print("Empty BST")
    else:
        while(node.leftchild!=None):
            node=node.leftchild
        print(node.data)
        return (node)

so, with help in the comment section. I completed the code. Thanks a lot, guys.

should I use del or not Is the use of del bad?

complexity is quite okay.