Why do I need to recursively return nodes when deleting from a binary search tree?

Question

I'm trying to implement the delete function of a binary search tree. The logic makes sense to me, but I'm having trouble understanding why my code doesn't seem to work. The difference I found was that returning the changes recursively from the bottom up seems to work, but simply removing the node when found doesn't. Could anyone help shed light on this?

My code (and what makes most sense to me)

def _delete(self, root, value):
    if root is None: 
    return

    if value < root.data:
        self._delete(root.left, value)         
    elif value > root.data:
        self._delete(root.right, value)     
    else:          
        if root.left is not None and root.right is not None: 
            root.data = self._find_min_value(root.right)    
            self._delete(root.right, root.data) 
        elif root.left is not None:         
            root = root.left
        else:                             
            root = root.right

The solution I found

def _delete(self, root, value):
    if root is None: 
        return

    if value < root.data:
        root.left = self._delete(root.left, value)        
    elif value > root.data:
        root.right = self._delete(root.right, value)    
    else:          
        if root.left is not None and root.right is not None: 
            root.data = self._find_min_value(root.right)    
            root.right = self._delete(root.right, root.data)  
        elif root.left is not None:         
            return root.left
        else:                           
            return root.right
    return root

Vil · Accepted Answer · 2018-08-18 22:58:27Z

This is due to the way assignment works in Python. The culprits are the lines root = root.left and root = root.right. What you want it to do is to change the location in memory that root is pointing at to another value. What Python does is simply assigning the name root to a different value, so the original location in memory that root was pointing to remains unchanged.

To make it simpler, you have a similar scenario to the following code

arr = [1,2]
root = arr[1]
root = arr[2]

Here arr remains untouched and the name root is simply assigned different values. This is why in the second implementation which works you only reassign class members of root.

Collectives™ on Stack Overflow

Why do I need to recursively return nodes when deleting from a binary search tree?

1 Answer 1

Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Related