Idea

This brings me back to my university time when we were forced to manually implement heap……

However, this one is simpler but still, not an easy task to do.

Basically, the deletion can be divided into two stages:

Search for a node to remove.

If the node is found, delete the node.

The searching part is easy, let’s skip it.

How do we delete a node?

trivial case: the node is a leaf node, just delete it.
if the node to be deleted has a right subtree, find the successor, swap them and delete the node again (recursively) in the right subtree.
if the node does not have a right subtree, find the predecessor, swap them and delete the node again (recursively) in the left subtree.

One thing that confused me a little bit is: why can we do 2 and 3?

You can try to flatten the tree and the answer is obvious (by flatten I mean in-order traversal), the predecessor and the successor are next to the node to be deleted, so swap them will not break the BST property for the subtree (the original BST is broken but eventually we will delete the node, so the original BST will be ok eventually).

Algorithm

To find successor, go right once and keep going left.

1
2
3
4
5


def successor(node):
    head=node.right
    while head.left:
        head=head.left
    return head

To find predecessor, go left once and keep going right.

1
2
3
4
5


def predecessor(node):
    head=node.left
    while head.right:
        head=head.right
    return head

With these and simple recursion, we can solve the problem.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32


class Solution:
    def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
        def successor(node):
            head=node.right
            while head.left:
                head=head.left
            return head
        
        def predecessor(node):
            head=node.left
            while head.right:
                head=head.right
            return head

        if not root:
            return None
        if root.val<key:
            root.right=self.deleteNode(root.right,key)
        elif root.val>key:
            root.left=self.deleteNode(root.left,key)
        else:
            if not root.left and not root.right:
                return None
            if root.right:
                succ=successor(root)
                root.val=succ.val
                root.right=self.deleteNode(root.right,succ.val)
            elif root.left:
                pred=predecessor(root)
                root.val=pred.val
                root.left=self.deleteNode(root.left,pred.val)
        return root

Idea#

Algorithm#

Idea

Algorithm