Problem Statement in English

Heh, that’s the neat part :)) You delete a node from a BST, ahaha.

In case you’re wondering what a BST is, the every node to the left (makes up the left subtree) of any node has elements smaller than it, and every node in the right subtree is bigger than it.

Needless to say, we must preserve this property when we delete the target node.

Approach

We’ll look at this case wise:

  • Case 1: The target node doesn’t exist
    In this case, we return the tree as is.

  • Case 2: The target node exists and has no left or right subtree (no children)
    We can remove the target node with no worry about consequences.

  • Case 3: The target node has either a left or right subtree
    We can replace this node with whichever subtree is non null.

  • Case 4 (tricky): Ahem, both left and right subtree exist
    This is non trivial. You have 2 options, replace the target node with the largest element from the left subtree (of the target node), or smallest element from right subtree (of the target node). Why?

Think about the properties of a BST. If you want to replace the target node with a new node, then the new node must be greater than every node of the left subtree, and lesser than every node of the right subtree. Yes?

Now let’s consider why the greatest node of the left subtree. The greatest node of the left subtree will be larger than every node in the left subtree, and yet, it is guaranteed to be smaller than every node of the right subtree, since it is going to be smaller than the node we’re replacing, which in turn, is smaller than every node in the right subtree. Hence the structural property of the BST is preserved.

Similarly, the smallest node of the right subtree will still be larger than every node in the left subtree of the node it replaces, and yet be smaller than every node in the right subtree it belonged to.

That brings us to the last part of this case - “belonged to”. You see, the node we use to replace the target node must be removed from its position, since we can’t have 2 instances of it. We are after all using it to replace the target node, not copy into.

Hence, we apply this same delete function on the node we use to replace the target node. And this in turn, when done recursively, will trigger a chain event, where every time a node is replaced, the replacer is deleted, and this propagates until necessary.

Step 1: Find the target node

temp = root
if temp.val < key and temp.right is not None:
    temp.right = self.deleteNode(temp.right, key)
elif temp.val < key and temp.right is None:
    return temp
elif temp.val > key and temp.left is not None:
    temp.left = self.deleteNode(temp.left, key)
elif temp.val > key and temp.left is None:
    return temp

  • Step 1.1.1: If temp is too small, we go right, else we go left
    We do this recursively, because we’re going to return the updated tree as we pop the recursion stack on our way back.

  • Step 1.1.2: If temp does not exist, we return the node, and hence its subtree as is
    No deletions need to occur in this tree since the target doesn’t exist in it.

Step 2: We found the node, now replace it

elif temp.val == key:
    # we found the key

    # if the right subtree doesn't exist, but left does
    if temp.right is None and temp.left is not None:
        return temp.left
    # if the left subtree doesn't exist, but right does
    elif temp.left is None and temp.right is not None:
        return temp.right
    # neither subtrees exist
    elif temp.left is None and temp.right is None:
        return None
    else:
        # both left and right subtrees exist

        # we choose to find the greatest element from
        # the right subtree to replace this node with
        assert temp.left != None
        replaceWith = self.findGreatestNode(temp.left)
        temp.val = replaceWith

        # now we've to delete the node from its original place since we moved it elsewhere
        temp.left = self.deleteNode(temp.left, replaceWith)

return root

  • Step 2.1.1: If the right subtree doesn’t exist, but the left one does, return it
    This results in the target node being replaced by its left subtree.

  • Step 2.1.2: If the left subtree doesn’t exist, but the right one does, return it
    This results in the target node being replaced by its right subtree.

  • Step 2.1.3: If neither left, nor right subtree exists return null
    This results in the target node being replaced by null, essentially removing it from the tree altogether, as its parent now points to null instead of the target node.

  • Step 2.1.4.1: If left and right subtree exists, find either the greatest node of the left subtree, or smallest node of the right subtree and replace the target node with it

  • Step 2.1.4.2: Delete the node we’re repalacing target with from its original place
    This requires that we call the same function, but with the root node as either the left or right subtree’s root, depending on which approach you went with (I chose to use the greatest element from the left subtree, so I’ll be deleting the node from the left subtree).

Step 3: Keep returning the updated subtrees until we’ve reached the original root.

Then return the original root as that will be the final updated BST.

Solution in Python


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
        if root is None:
            return root

        temp = root

        # recursively call the function till we find the desired key
        # or report that it doesn't exist in the tree (by just popping the stack and returning each node as is)
        if temp.val < key and temp.right is not None:
            temp.right = self.deleteNode(temp.right, key)
        elif temp.val < key and temp.right is None:
            return temp
        elif temp.val > key and temp.left is not None:
            temp.left = self.deleteNode(temp.left, key)
        elif temp.val > key and temp.left is None:
            return temp
        elif temp.val == key:
            # we found the key

            # if the right subtree doesn't exist, but left does
            if temp.right is None and temp.left is not None:
                return temp.left
            # if the left subtree doesn't exist, but right does
            elif temp.left is None and temp.right is not None:
                return temp.right
            # neither subtrees exist
            elif temp.left is None and temp.right is None:
                return None
            else:
                # both left and right subtrees exist

                # we choose to find the greatest element from
                # the right subtree to replace this node with
                assert temp.left != None
                replaceWith = self.findGreatestNode(temp.left)
                temp.val = replaceWith

                # now we've to delete the node from its original place since we moved it elsewhere
                temp.left = self.deleteNode(temp.left, replaceWith)

        return root

    def findGreatestNode(self, root: TreeNode) -> int:
        temp = root

        # keep going right while you can
        while temp.right:
            temp = temp.right

        # greatest possible value
        return temp.val

Complexity

  • Time: $O(\text{height of the tree})$

Since we traverse the BST using the left right technique, we only need to visit as many nodes as the height of the tree in the worst case.

It is actually twice the height, since we go down and come back up, but in Big O notation we can ignore this.

  • Space: $O(\text{height of tree})$

We are using a recursion stack that can get as large as the number of nodes we visit - which is the height of the tree in the worst case.

Mistakes I Made

I completely misjudged the process in case 4. What’s more, I tried to do this iteratively and quickly realized that I would need to store a reference to the node prior to the target node in order to delete it, and even then, the task is just so much harder with that approach.

And we are done.