450. Delete Node in a BST

[songyy5517]

Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST. Basically, the deletion can be divided into two stages:

1. Search for a node to remove.
2. If the node is found, delete the node.

Example 1:

Input: root = [5,3,6,2,4,null,7], key = 3
Output: [5,4,6,2,null,null,7]
Explanation: Given key to delete is 3. So we find the node with value 3 and delete it.
One valid answer is [5,4,6,2,null,null,7], shown in the above BST.
Please notice that another valid answer is [5,2,6,null,4,null,7] and it's also accepted.

Example 2:

Input: root = [5,3,6,2,4,null,7], key = 0
Output: [5,3,6,2,4,null,7]
Explanation: The tree does not contain a node with value = 0.

Example 3:

Input: root = [], key = 0
Output: []

Intuition The problem can be basically split into two subtasks. The first is to locate the given node. The second one is to delete it from the whole tree. Therefore, we can first search for the target node in the whole tree. If not exists, return the root node; otherwise, we delete it from the tree. To implement the delete operation, we need to keep a pointer to the parent node of the target node. Then we perform different delete operation according to whether the target node has a right substree.

[songyy5517]

Approach: Discuss by case

1. Exception handling;
2. Define a pointer head to the parent node, and a boolean variable left to record whether the current node is a left child;
3. Search for the target node in the tree and update the pointer to the parent node of the current node;
4. If the target node doesn't exist, then return the root node;

5. Otherwise, delete the target node from the tree: （1）If the target node has a right subtree, then

   • Find the bottom left node in its right substree;
   • Move the left subtree of the target tree as the left subtree of the leftmost node;
   • Move the right subtree of the target node as the child of the parent node of the target node;

   （2）Otherwise, we move the left subtree of the target node as the child of the parent node of the target node;

6. If the parent node is unchanged, return its right child; otherwise, return the root node.

Complexity Analysis

• Time complexity: $O(N)$ , the binary tree would degenerate into a linked list in the worst case, so the search process would take $O(N)$ time.
• Space complexity: $O(1)$ , additionally define constant-level variables.

[songyy5517]

class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        // Intuition: Locate & Delete. First, we need to locate the given node.
        // If exists, then delete it. The key here is how to realize the delete operation.
        // 1. Exception handling
        if (root == null)
            return null;

        // 2. Locate the given node
        TreeNode target = root, head = new TreeNode(Integer.MIN_VALUE);
        head.right = target;
        Boolean left = false;    // indicates whether it is the left son of its father node

        while (target != null && target.val != key){
            head = target;
            if (target.val > key){
                target = target.left;
                left = true;
            }
            else{ 
                target = target.right;
                left = false;
            }
        }

        if (target == null)
            return root;

        // 3. Delete the target node
        // If the target node has the right substree
        if (target.right != null){
            TreeNode t_left = target.left, t_right = target.right;
            TreeNode last_node = t_right;
            // Get the minimal node in the right subtree
            while (last_node.left != null)
                last_node = last_node.left;
            if (left)
                head.left = t_right;
            else 
                head.right = t_right;
            last_node.left = t_left;
        }
        else {
            if (left)
                head.left = target.left;
            else
                head.right = target.left;
        }

        return head.val == Integer.MIN_VALUE ? head.right : root;
    }
}

[songyy5517]

2024/6/12