LeetCode 450. Delete Node in a BST

https://leetcode.com/problems/delete-node-in-a-bst/

Intuition

• Node is a leaf, and one could delete it straightforward

• Node is not a leaf and has a right child. Then the node could be replaced by its successor which is somewhere lower in the right subtree. Then one could proceed down recursively to delete the successor.

• Node is not a leaf, has no right child and has a left child. That means that its successor is somewhere upper in the tree but we don’t want to go back. Let’s use the predecessor here which is somewhere lower in the left subtree. The node could be replaced by its predecessor and then one could proceed down recursively to delete the predecessor.

Algorithm

• If key > root.val then delete the node to delete is in the right subtree root.right = deleteNode(root.right, key).
• If key < root.val then delete the node to delete is in the left subtree root.left = deleteNode(root.left, key).
• If key == root.val then the node to delete is right here. Let’s do it :
  • If the node is a leaf, the delete process is straightforward : root = null.
  • If the node is not a leaf and has the right child, then replace the node value by a successor value root.val = successor.val, and then recursively delete the successor in the right subtree root.right = deleteNode(root.right, root.val).
  • If the node is not a leaf and has only the left child, then replace the node value by a predecessor value root.val = predecessor.val, and then recursively delete the predecessor in the left subtree root.left = deleteNode(root.left, root.val).
• Return root.

Java Solution

class Solution {
    public int predecessor(TreeNode root) {
        root = root.left;
        while (root.right != null) {
            root = root.right;
        }
        return root.val;
    }
    
    public int successor(TreeNode root) {
        root = root.right;
        while (root.left != null) {
            root = root.left;
        }
        return root.val;
    }
    public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null) return null;
        
        if (key > root.val) {
            root.right = deleteNode(root.right, key);
        } else if (key < root.val) {
            root.left = deleteNode(root.left, key);
        } else {
            if (root.left == null && root.right == null) {
                root = null;
            } else if (root.right != null) {
                root.val = successor(root);
                root.right = deleteNode(root.right, root.val);
            } else {
                root.val = predecessor(root);
                root.left = deleteNode(root.left, root.val);
            }
        }
        return root;
    }
}