struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int val) : val(val), left(nullptr), right(nullptr) {}
};

TreeNode* deleteNode(TreeNode* root, int key) {
    TreeNode* parent = nullptr;
    TreeNode* curr = root;
    while (curr != nullptr && curr->val != key) {
        parent = curr;
        curr = (key < curr->val) ? curr->left : curr->right;
    }
    if (curr == nullptr) {
        return root;
    }
    if (curr->left != nullptr && curr->right != nullptr) {
        parent = curr;
        TreeNode* succ = curr->right;
        while (succ->left != nullptr) {
            parent = succ;
            succ = succ->left;
        }
        curr->val = succ->val;
        curr = succ;
    }
    TreeNode* child = (curr->left != nullptr) ? curr->left : curr->right;
    if (parent == nullptr) {
        root = child;
    } else if (parent->left == curr) {
        parent->left = child;
    } else {
        parent->right = child;
    }
    delete curr;
    return root;
}
More from Binary Search Trees
