Delete Node in a BST

Problem Id: 450 Difficulty: Medium Tag: Tree


Intuition

This problem could be solved by following steps.

  1. Find the node which would be removed and its parent. If its parent is None, then the node itself is the root node.

  2. Find the biggest node in the sub-tree of the tobe-removed node and its parent. The tobe-removed node would be replaced with this node. And the node itself would be replaced by its left sub-tree.

    If the tobe-removed node has no left sub-tree, then it could be replaced directly by its right sub-tree.

Solution


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


class Solution:
    def deleteNode(self, root: TreeNode, key: int) -> TreeNode:
        # Find the tobe-removed node and its parent
        removed = root
        removed_parent = None
        while removed and removed.val != key:
            removed_parent = removed
            removed = removed.left if removed.val > key else removed.right
        if removed is None:
            # Could not find the key node
            return root

        if removed.left is None:
            if removed_parent is None:
                return removed.right
            elif removed_parent.left is removed:
                removed_parent.left = removed.right
            else:
                removed_parent.right = removed.right
            return root
        else:
            # Find the biggest value in the removed's left tree
            biggest = removed.left
            biggest_parent = removed
            while biggest.right:
                biggest_parent = biggest
                biggest = biggest.right
            if biggest_parent is removed:
                biggest_parent.left = biggest.left
            else:
                biggest_parent.right = biggest.left
            biggest.left, biggest.right = removed.left, removed.right
            if removed_parent is None:
                return biggest
            if removed_parent.left is removed:
                removed_parent.left = biggest
            else:
                removed_parent.right = biggest
            return root