450. Delete Node in a BST - cocoder39/coco39_LC GitHub Wiki

450. Delete Node in a BST

Notes 2022 Cases:

1. node doesn't have left or right - return null
2. node only has left subtree- return the left subtree
3. node only has right subtree- return the right subtree
4. node has both left and right - find the minimum value in the right subtree, set that value to the currently found node, then recursively delete the minimum value in the right subtree. the successor of the node to be deleted is the next greater value (min in right subtree). We can also consider the predecessor which is the max int the left subtree.

class Solution:
    def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
        if not root:
            return root
        elif root.val > key:
            root.left = self.deleteNode(root.left, key)
        elif root.val < key:
            root.right = self.deleteNode(root.right, key)
        elif not root.left:
            return root.right
        elif not root.right:
            return root.left
        else:
            root.val = self.findMin(root.right)
            root.right = self.deleteNode(root.right, root.val)
        return root

    def findMin(self, root: TreeNode) -> int:
        while root.left:
            root = root.left
        return root.val

====================================================================

time is O(height) and space for call stack is O(height)

class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        if (! root) {
            return nullptr;
        } else if (root->val < key) {
            root->right = deleteNode(root->right, key);
        } else if (root->val > key) {
            root->left = deleteNode(root->left, key);
        } else { // root->val == key
            if (! root->left) {
                return root->right;
            } else if (! root->right) {
                return root->left;
            } else {
                root->val = findMin(root->right);
                root->right = deleteNode(root->right, root->val);
            }
        }
        return root;
    }
private:
    int findMin(TreeNode* root) {
        int res = root->val;
        while (root) {
            res = root->val;
            root = root->left;
        }
        return res;
    }
};