"Understanding the deletion process for a node with two child nodes in a binary search tree"

In the given code, there is a binary search tree implemented using the nodes and binary classes. The delete method in the binary class is used to delete a node from the tree. I would like to understand how the def _delete_recursive() function works when deleting a node that has two child nodes.

Could you please provide an explanation of the deletion process in this case? Specifically, how does the function handle the situation where the node to be deleted has two child nodes? I would appreciate a step-by-step breakdown of the process and the code is

class nodes:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

class binary:
    def __init__(self):
        self.root = None

    def insert(self, value):
        self.root = self.insert_recur(value, self.root)

    def insert_recur(self, value, curr):
        if curr is None:
            return nodes(value)
        elif curr.value < value:
            curr.right = self.insert_recur(value, curr.right)
        elif curr.value > value:
            curr.left = self.insert_recur(value, curr.left)
        return curr

    def trans(self):
        self.print_trans(self.root)

    def print_trans(self, node):
        if node is None:
            return
        self.print_trans(node.left)
        print("----->", node.value,end=" ")
        self.print_trans(node.right)

    def delete(self, value):
        self.root = self._delete_recursive(value, self.root)
    
    def _delete_recursive(self, value, node):
        if node is None:
            return node
        if value < node.value:
            node.left  = self._delete_recursive(value,node.left)
        elif value > node.value:
            node.right  = self._delete_recursive(value,node.right)
        else:
            if node.left is None and node.right is None :
                return None
            elif node.right is None:
                return node.left
            elif node.left is None:
                return node.right  
        return node
    
 
tree = binary()
tree.insert(1)
tree.insert(2)
tree.insert(3)
tree.insert(4)
tree.insert(5)
tree.insert(6)
tree.insert(7)
tree.insert(8)
tree.insert(9)
tree.insert(10)
tree.insert(11)
tree.insert(12)
tree.insert(13)
tree.insert(14)
tree.insert(15)
tree.insert(16)
tree.insert(17)
tree.delete(5)
tree.trans()

I plan to ask this question on Stack Overflow to seek a clear explanation.

"I have been working on a binary search tree implementation using the nodes and binary classes. I'm currently trying to understand the deletion process for a node that has two child nodes.

I have examined the code and the _delete_recursive function. From my understanding, the function handles the cases where the node to be deleted has no children or only one child node. However, I'm having difficulty comprehending how it handles the situation where the node has two child nodes.

I expected that the _delete_recursive function would provide a step-by-step explanation of how it handles the deletion process for a node with two child nodes. Specifically, I would like to know how it selects the successor node and updates the tree structure accordingly.

I would greatly appreciate any insights or explanations on how the _delete_recursive function works in this scenario. Thank you!"

> I'm having difficulty comprehending how it handles the situation where the node has two child nodes.

The answer is simple: it doesn't handle that case.

> I would like to know how it selects the successor node and updates the tree structure accordingly.

It doesn't select the successor node and doesn't update the tree in that case.

The driver code you have provided doesn't really test this case. The tree that the main code creates looks like one chain:

   1
    \
     2
      \
       3
        \
         4
          \
           5
            \
            ...
              \
               17

And so the call to tree.delete(5) works fine, as it is not a node that has two children.

To really test that case, create a tree like this:

       4
      / \
     2   6
    / \
   1   3

...and then try to delete the node with value 2:

tree = binary()
tree.insert(4)
tree.insert(2)
tree.insert(6)
tree.insert(1)
tree.insert(3)
tree.delete(2)

...and now you'll see the node 2 is still in the tree.

You'll need to look for a better implementation. Some references:

• Wikipedia explains the process for the case where a node has two children, and provides pseudo code for it.
• There are many Python implementations on this site. Here is a list of answers where I posted such myself -- each time a little different, as it usually starts from the asker's code: here, here, here, here, here...