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

When the node we want to delete has no child (it's working fine)
When the node we want to delete has one child (it's working fine)
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,

correct method to delete the node from BST
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.
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 :)

@Jake Steele No, brother. I am just learning data-structures using python through the internet, I like to code myself first and I can't understand what's wrong with my code. — Siddhesh Sharma
– Siddhesh Sharma, Commented Jun 6, 2018 at 21:41
Usually when implementing the last section in delete in bst you do not really delete the node, you just replace it value with the value of the minimum from the right, like you did, and call the delete function on that minimum. — Yonlif
– Yonlif, Commented Jun 6, 2018 at 23:08

Siddhesh Sharma · Accepted Answer · 2018-06-07 05:31:36Z

    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.

Great job answering yourself! (Got an upvote). About the del, as mentioned in the comments it is not needed, also you can just replace the node with None as done in the implementation of geeksforgeeks. About the time complexity, if you are learning DAST on your on you might want to try and calculate it by your self just for the experience and understanding. Good luck!

Collectives™ on Stack Overflow

How to delete a node in Binary Search Tree using Python

1 Answer 1

1 Comment

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Linked

Related