Delete Node in a BST

Intuitiondeletion is a local reconnection that follows the BST search path

The BST ordering tells you where the key can be: smaller keys are in the left subtree and larger keys are in the right subtree. Follow that rule until you find the node or reach a null pointer. Every recursive call returns the root of its subtree after the deletion, so the parent can reconnect its left or right link to that returned root.

Once the target is found, its children determine the repair. A leaf returns null. A node with one child returns that child, allowing the parent to bypass the deleted node. With two children, neither child can simply replace the node without disturbing ordering. Copy the smallest value from the right subtree into the target, then delete that successor from its original position; the successor has no left child, so the difficult case becomes a one-child or leaf case.

Approacheach returned subtree root carries the repair back to its parent

1. 1Return null when the current root is null, because an empty subtree contains no key and must remain empty.
2. 2If key is smaller than root->val, recursively delete from the left subtree and assign the returned pointer to root->left; without the assignment, the parent would keep pointing at the deleted subtree root.
3. 3If key is greater than root->val, do the symmetric operation on root->right; the BST property makes this the only branch that can contain the key.
4. 4When the values match, return the non-null child if one side is empty, or return null for a leaf; this bypasses the current node while preserving the entire remaining subtree.
5. 5When both children exist, walk left from root->right to find the smallest value in the right subtree, because that value is larger than every value on the left and no larger than any other value on the right.
6. 6Copy the successor value into the current node, then recursively delete that value from root->right and return root; this removes the duplicate successor while keeping the current node connected to both subtrees.

Complexitythe height, not the total node count, controls the work

Annotated solutionC++ · recursive · subtree roots carry deletion back upward

#include <vector>

using namespace std;

class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        if (root == nullptr) {
            return nullptr;
        }

        if (key < root->val) {
            root->left = deleteNode(root->left, key);
        } else if (key > root->val) {
            root->right = deleteNode(root->right, key);
        } else {
            if (root->left == nullptr) {
                TreeNode* child = root->right;
                delete root;
                return child;
            }

            if (root->right == nullptr) {
                TreeNode* child = root->left;
                delete root;
                return child;
            }

            TreeNode* successor = root->right;
            while (successor->left != nullptr) {
                successor = successor->left;
            }

            root->val = successor->val;
            root->right = deleteNode(root->right, successor->val);
        }

        return root;
    }
};

The key placement is the assignment after each recursive call. Deleting a node can change the root pointer of that subtree: a leaf becomes null, or a one-child node is replaced by its child. Writing root->left = or root->right = stores that changed pointer in the parent. The two-child case deliberately copies only the value, then lets the same method remove the original successor node.

The iterative alternativean O(1)-extra-space arrangement when recursion depth matters

You can perform the same operation with parent and current pointers instead of recursive calls. This is an optimisation for extra space in a deep tree: the search and successor walk still take O(h) time, but the algorithm uses O(1) auxiliary space. The tradeoff is more pointer bookkeeping, especially when the node being removed is the root.

#include <vector>

using namespace std;

class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        TreeNode* parent = nullptr;
        TreeNode* current = root;

        while (current != nullptr && current->val != key) {
            parent = current;
            if (key < current->val) {
                current = current->left;
            } else {
                current = current->right;
            }
        }

        if (current == nullptr) {
            return root;
        }

        if (current->left != nullptr && current->right != nullptr) {
            TreeNode* successorParent = current;
            TreeNode* successor = current->right;

            while (successor->left != nullptr) {
                successorParent = successor;
                successor = successor->left;
            }

            current->val = successor->val;
            parent = successorParent;
            current = successor;
        }

        TreeNode* child = current->left != nullptr
            ? current->left
            : current->right;

        if (parent == nullptr) {
            root = child;
        } else if (parent->left == current) {
            parent->left = child;
        } else {
            parent->right = child;
        }

        delete current;
        return root;
    }
};

Common mistakesspecific pointer and successor errors that survive simple tests