L44. Delete a Node in Binary Search Tree | BST

Deleting a node from a Binary Search Tree (BST) while maintaining the BST property (left child smaller than root, right child greater than root) requires careful restructuring of the tree. This guide breaks down the problem, the core mental models, step-by-step algorithms, and complete C++ and Java implementations.

1. Why Do We Need Node Deletion in a BST?

• Dynamic Data Structures: Real-world data is constantly changing; we need the ability to insert, search, and delete elements efficiently.
• Preserving Invariants: Simply removing a node can break the BST property. Proper rearrangement ensures that subsequent searches remain $O(\log n)$ on average.
• Handling Edge Cases: Leaf nodes are trivial to delete, but removing nodes with one or two children requires precise pointer redirection.

2. Core Mental Model: The Connecting Strategy

Imagine you want to remove a specific node (e.g., node 8) from a BST. If you just delete it, its left and right subtrees are left floating.

To bridge the gap cleanly without violating BST rules:

• Find the rightmost node of the left subtree: The greatest element in the left subtree can safely replace the deleted node because it is larger than all other nodes in that left subtree and smaller than everything in the right subtree.
• Alternative approach: Take the entire left subtree and attach it to the extreme left of the right subtree.

3. Naive vs. Better Approach

4. Step-by-Step Algorithm Walkthrough

1. Base Case Check:
   • If the root is null, return null.
   • If the root's value matches the key to delete, execute the deletion helper function.
2. BST Navigation:
   • If the key is less than root.val, move to the left subtree (root.left = deleteNode(root.left, key)).
   • If the key is greater than root.val, move to the right subtree (root.right = deleteNode(root.right, key)).
3. The Helper Re-attachment Logic:
   • When we find the node to delete (root), we check if its left or right child is missing. If one is missing, we can simply return the other child.
   • If both children exist:
     • Grab the entire left subtree.
     • Find the extreme left node of the right subtree.
     • Attach the left subtree to that extreme left node's left pointer.
     • Return root.right as the new root of this subtree.

5. Complete Flow Walkthrough

Suppose we want to delete node 5 from the following BST structure:

        8
       / \
      3   10
     / \    \
    1   6    14
       / \
      4   7

1. Locate Target: Start at root 8. Since $5 < 8$, go left to 3. Since $5 > 3$, go right to 6. Since $5 < 6$, go left to 5. Target found!
2. Apply Helper Function:
   • Left subtree of 5 is node 4.
   • Right subtree of 5 is node 7.
   • Take left subtree (4) and attach it to the extreme left of the right subtree (7).
   • Return root.right (7) to replace node 5.
3. Updated Subtree: Node 6 now points to 7 (which carries along its attached left subtree containing 4).

        8
       / \
      3   10
     / \    \
    1   6    14
         \
          7
         /
        4

6. C++ Implementation

class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        if (root == nullptr) {
            return nullptr;
        }
        
        // If the root itself is the node to be deleted
        if (root->val == key) {
            return helper(root);
        }
        
        TreeNode* dummy = root;
        while (root != nullptr) {
            if (root->val > key) {
                if (root->left != nullptr && root->left->val == key) {
                    root->left = helper(root->left);
                    break;
                } else {
                    root = root->left;
                }
            } else {
                if (root->right != nullptr && root->right->val == key) {
                    root->right = helper(root->right);
                    break;
                } else {
                    root = root->right;
                }
            }
        }
        return dummy;
    }
    
    TreeNode* helper(TreeNode* root) {
        if (root->left == nullptr) {
            return root->right;
        } else if (root->right == nullptr) {
            return root->left;
        }
        
        TreeNode* rightChild = root->right;
        TreeNode* lastRight = findLastRight(root->left);
        lastRight->right = rightChild;
        return root->left;
    }
    
    TreeNode* findLastRight(TreeNode* root) {
        if (root->right == nullptr) {
            return root;
        }
        return findLastRight(root->right);
    }
};

7. Java Implementation

class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null) {
            return null;
        }
        
        if (root.val == key) {
            return helper(root);
        }
        
        TreeNode dummy = root;
        while (root != null) {
            if (root.val > key) {
                if (root.left != null && root.left.val == key) {
                    root.left = helper(root.left);
                    break;
                } else {
                    root = root.left;
                }
            } else {
                if (root.right != null && root.right.val == key) {
                    root.right = helper(root.right);
                    break;
                } else {
                    root = root.right;
                }
            }
        }
        return dummy;
    }
    
    private TreeNode helper(TreeNode root) {
        if (root.left == null) {
            return root.right;
        } else if (root.right == null) {
            return root.left;
        }
        
        TreeNode rightChild = root.right;
        TreeNode lastRight = findLastRight(root.left);
        lastRight.right = rightChild;
        return root.left;
    }
    
    private TreeNode findLastRight(TreeNode root) {
        if (root.right == null) {
            return root;
        }
        return findLastRight(root.right);
    }
}

8. Complexity Analysis

• Time Complexity: $O(H)$, where $H$ is the height of the binary search tree. In the worst case (skewed tree), it takes $O(N)$ time. In a balanced BST, it takes $O(\log N)$ time.
• Space Complexity: $O(1)$ auxiliary space (iterative approach with pointer adjustments) or $O(H)$ if considering the recursive call stack for traversal and helper lookups.

Summary and Key Takeaways

• BST Property Maintenance: Deleting a node must never violate the invariant that left children are smaller and right children are larger than the parent.
• Three Core Scenarios:
  1. Node has no children (leaf): simply remove it.
  2. Node has one child: replace the node with its single child.
  3. Node has two children: graft the left subtree onto the extreme right/left of the right subtree.
• Helper Function Isolation: Encapsulating the re-attachment logic keeps the traversal and deletion clean and modular.
• Pointer Efficiency: Manipulating references directly avoids extra memory allocation, achieving $O(1)$ auxiliary space.
• Recursive vs. Iterative: Both patterns work well, but understanding pointer updates prevents dangling references or memory leaks.