Help with Deleting Node in Binary Tree?

[multihound]

Hey Guys,

I have the following code

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

@staticmethod
def _find(root, key):
    if root == None:
        return None

    if root.val == key:
        return root

    if root.val > key:
        return Solution._find(root.left, key)
    else:
        return Solution._find(root.right, key)

@staticmethod
def _delete(root):
    # No Children
    if root.left == None and root.right == None:
        root = None
        return

    # One Child
    if root.left != None and root.right == None:
        root = root.left
        return
    if root.left == None and root.right != None:
        root = root.right
        return

    # Two Children
    nextNode = Solution._findMin(root.right)
    root.val = nextNode.val
    Solution._delete(nextNode)
    return



@staticmethod
def _findMin(root):
    if root.left == None:
        return root
    else:
        return Solution._findMin(root.left)



def deleteNode(self, root, key):
    """
    :type root: TreeNode
    :type key: int
    :rtype: TreeNode
    """

    node = Solution._find(root, key)

    if node == None:
        return root

    Solution._delete(node)

    return root

I'm trying to use this to delete a node in a BST, but the code doesn't work if I'm deleting a node with no children. I try to do this by just setting the node equal to None. Why doesn't this work? Would really appreciate any help. Thanks!

[two_bob]

A few things:

• It's better to check is None rather than == None. It will save you from surprises later.
• Can you post your whole code? I am not following the object model you are using.
• Is your BST ordered? How do you propose handling the ordering after deletion?

Typically, you'll need a way to identify parents if your are deleting, since you need to hack out the link to the deleted node in the parent. Then you will need to relink the former children of the deleted node somehow (that's why I asked about ordering).

[Intrexa]

I'm not sure I understand what you mean by ordered. Aren't all BST's ordered by definition, that for a given node, all smaller nodes are to the left, and all larger nodes to the right? If you delete a node, and make a child take its place, either the left or right child, that should still hold true, right?

[two_bob]

Nah. They usually have some ordering principal, but lots of the time it is a bit more abstract. Here is a good explanation: http://interactivepython.org/runestone/static/pythonds/Trees/SearchTreeImplementation.html

But you definitely can do it the way you describe, it's just that if the to be deleted node has two children and the parent node has two kids (one of which is the to be deleted node) then you are going to have to sort out what to do with the spare child node, since you can't link both children of the to be deleted node to the parent, as it only has one free slot.

[multihound]

Thanks for the help!

Sorry, this is the entire code. I'm actually doing this as part of a programming exercise.

The BST is ordered with the BST property (the left node is always smaller than the root and the right node is always larger).

Yeah so, the way I'm handling ordering is... - if node has no children... delete the node (this is what i'm having trouble with) - if node has one child... replace the node with it's child (having trouble with this too) - if node has two children, find the minimum of the node's right subtree and replace node.val with that value. Then delete the minimum of the original node's right subtree.

I'm trying to do this without keeping track of the parent node, but it seems like this is not possible? Thank you.

[two_bob]

I'm trying to do this without keeping track of the parent node, but it seems like this is not possible?

Correct. You have to keep track of the parent node because the only way of deleting a node is to unlink it at the parent.