Deleting a node with two children in BST-CodePudding

I have implemented a binary search tree and it is working fine except for the case where I have to delete a node with two children. The following is my code for the delete method:

def find(self, node):
        curr = node
        while curr.left is not None:
            curr = curr.left
        return curr

def delete(self, key):
        node_to_remove = self._search(key, self.root)
        if node_to_remove.left is None and node_to_remove.right is None:
            #Then we identify this as a leaf node
            if node_to_remove is node_to_remove.parent.left:
                #Setting the parent's reference to this to None
                node_to_remove.parent.left = None 
            elif node_to_remove is node_to_remove.parent.right:
                node_to_remove.parent.right = None
                
                
        #2nd Case --> Two child
        elif node_to_remove.left and node_to_remove.right:
            minimum = self.find(node_to_remove.right)
            node_to_remove = minimum
            self.delete(minimum.key)
            
        #3rd Case -> One child
        else:
            if node_to_remove.left:
                node_to_remove.left.parent = node_to_remove.parent
                node_to_remove.parent.left = node_to_remove.left
            elif node_to_remove.right:
                node_to_remove.right.parent = node_to_remove.parent
                node_to_remove.parent.right = node_to_remove.right

Any indicators on how to fix the second case would be of immense help!

CodePudding user response：

You'll need to take the value of the deeper deleted node and assign it to the node that has the two children. So that block should look like this:

    elif node_to_remove.left and node_to_remove.right:
        minimum = self.find(node_to_remove.right)
        self.delete(minimum.key)
        node_to_remove.key = minimum.key

Other remarks

Your code will run into an exception when the root has the value to delete and it has no two children. In that case your code wants to access the parent node, which the root node does not have. Furthermore, such a deletion should result in a different value for this.root.

Here is the suggested correction:

    def delete(self, key):
        node_to_remove = self._search(key, self.root)
        if node_to_remove.left is None and node_to_remove.right is None:
            if node_to_remove is self.root:
                self.root = None
            elif node_to_remove is node_to_remove.parent.left:
                node_to_remove.parent.left = None 
            elif node_to_remove is node_to_remove.parent.right:
                node_to_remove.parent.right = None
                
                
        #2nd Case --> Two child
        elif node_to_remove.left and node_to_remove.right:
            minimum = self.find(node_to_remove.right)
            self.delete(minimum.key)
            node_to_remove.key = minimum.key
            
            
        #3rd Case -> One child
        else:
            if node_to_remove.left:
                node_to_remove.left.parent = node_to_remove.parent
                if node_to_remove is self.root:
                    self.root = node_to_remove.left
                else:
                    node_to_remove.parent.left = node_to_remove.left
            elif node_to_remove.right:
                node_to_remove.right.parent = node_to_remove.parent
                if node_to_remove is self.root:
                    self.root = node_to_remove.right
                else:
                    node_to_remove.parent.right = node_to_remove.right

A second remark: your tree is threaded (i.e. it has parent references). It is possible to do this for a non-threaded tree, and also with less code.