Binary search tree deletion function in Python

Simply put, you cannot assign anything to self. In Python, self is a reference to the object that you called the method on. It would not be None (so you don't need the if self is None check), and you cannot assign some other value to it.

However, when deleting a node from the tree, it is possible that the current node (the node which you called delete on) will be deleted. Instead of assigning values to self, we can make the delete return a node object. If the current node is not deleted, simply return itself; otherwise, return the node the will take its place (or None if the entire subtree is gone).

Here's the modified implementation, along with an insert method and a test case:

class Node:
    def __init__(self, key):
        self.left = self.right = None
        self.val = key

    def delete(self, key):
        """Delete a node with value `key`."""
        if key < self.val: 
            # Find and delete the value in the left subtree.
            if self.left is None:
                # There's no left subtree; the value does not exist.
                raise ValueError("Value not found in tree")
            self.left = self.left.delete(key)
            return self  # current node not deleted, just return
        elif key > self.val: 
            # Find and delete the value in the right subtree.
            if self.right is None:
                # There's no right subtree; the value does not exist.
                raise ValueError("Value not found in tree")
            self.right = self.right.delete(key)
            return self  # current node not deleted, just return
        else:
            # The current node should be deleted.
            if self.left is None and self.right is None:
                # The node has no children -- it is a leaf node. Just delete.
                return None

            # If the node has only one children, simply return that child.
            if self.left is None:
                return self.right
            if self.right is None:
                return self.left

            # The node has both left and right subtrees, and they should be merged.
            # Following your implementation, we find the rightmost node in the
            # left subtree and replace the current node with it.
            parent, node = self, self.left
            while node.right is not None:
                parent, node = node, node.right
            # Now, `node` is the rightmost node in the left subtree, and
            # `parent` its parent node. Instead of replacing `self`, we change
            # its attributes to match the value of `node`.
            if parent.left is node:
                # This check is necessary, because if the left subtree has only
                # node, `node` would be `self.left`.
                parent.left = None
            else:
                parent.right = None
            self.val = node.val
            return self

    def insert(self, key):
        if key < self.val:
            if self.left is None:
                self.left = Node(key)
            else:
                self.left.insert(key)
        else:
            if self.right is None:
                self.right = Node(key)
            else:
                self.right.insert(key)

def inorder_traverse(node):
    if node is None:
        return []
    ret = []
    if node.left is not None:
        ret += inorder_traverse(node.left)
    ret.append(node.val)
    if node.right is not None:
        ret += inorder_traverse(node.right)
    return ret

values = [5, 1, 2, 7, 3, 6, 4]
root = Node(values[0])
for x in values[1:]:
    root.insert(x)
print(inorder_traverse(root))

for x in values:
    root = root.delete(x)
    print(inorder_traverse(root))

The output is, as expected:

[1, 2, 3, 4, 5, 6, 7]
[1, 2, 3, 4, 6, 7]
[2, 3, 4, 6, 7]
[3, 4, 6, 7]
[3, 4, 6]
[4, 6]
[4]
[]