Unable to remove object after using del statement in python

Question

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

def contains(root, value):
    if root is None:
        return False

    if value == root.data:
        return True

    if value < root.data:
        return contains(root.left, value)
    else:
        return contains(root.right, value)


def insert(root, value):
    if root is None:
        root = BinaryNode(value)
    else:
        if value > root.data:
            if root.right is None:
                root.right = BinaryNode(value)
            else:
                return insert(root.right, value)
        else:
            if root.left is None:
                root.left = BinaryNode(value)
            else:
                return insert(root.left, value)

def getMin(root):
    if root.left is None:
        return root
    return getMin(root.left)

def remove(root, value):
    if root is None:
        return False
    elif value < root.data:
        remove(root.left, value)
    elif value > root.data:
        remove(root.right, value)
    else:
        if root.left is None and root.right is None:
            del root



def inorder(root):
    if root is not None:
        inorder(root.left)
        print(root.data)
        inorder(root.right)


b = BinaryNode(10)
insert(b, 9)
insert(b, 11)
insert(b,8)
insert(b,9.5)

remove(b, 9.5)
inorder(b)

i'm constructing the functions of a binary search tree. So far, in writing my remove function I handle the case in which the root to be removed from the tree is a left node (node without any children). For this, all I would have to do say del root. This has no effect at all on the tree and the value 9.5 still exists.

Preoccupied

del only removes the reference, here the local name root. It won't delete the b reference you have at the top. – Beekeeper

@MartijnPieters I have tried root = None as well. I see no other way of removing the root – Preoccupied

Remove is a bit complicated. Here is a good explanation: algolist.net/Data_structures/Binary_search_tree/Removal – Jameljamerson

Answer 1

del only removes the reference, here the local name root. It won't delete the b reference you have at the top. You can't do what you want with a function; a function doesn't own the references in the caller.

At most you can wrap your root value in a separate BinaryTree class instance, than can be 'empty'. Give it a root attribute and if that attribute is set to None the tree is cleared.

Beekeeper

Answer 2

This will nudge you in the right direction.

def remove(root, value):
    if root is None:
        return False
    elif root.left.data == value:
        root.left = None
    elif root.right.data == value:
        root.right = None
    elif value < root.data:
        remove(root.left, value)
    elif value > root.data:
        remove(root.right, value)

What Martijn refers to is another problem: Even with the above code, you cannot remove your root node. Only the nodes below. The answer to both problems lies in understanding the concept of references in python, and thinking what happens when you pass a reference to a function.

Pediatrics