Delete Node in a BST

Deleting a node from a Binary Search Tree requires careful handling of three cases: leaf nodes, nodes with one child, and nodes with two children. This solution maintains BST properties through strategic pointer reassignment and handles edge cases efficiently.

1. Problem Restatement

Clarifying questions to ask the interviewer:

1. Can we modify the input BST structure, or must we return a new tree?
2. What is the expected time complexity constraint? Are we aiming for O(log n) or O(n) worst case?
3. Should we handle duplicate values in the tree, and if so, how should they be treated?
4. What is the maximum size of the input BST? Will we have to handle large trees efficiently?
5. Do we need to maintain the BST property after deletion, or is it acceptable to return any valid BST?

Restatement of the problem in my own words:

Given a Binary Search Tree (BST) and a key value, I need to remove the node containing that key from the tree while maintaining the BST properties. The deletion should preserve the ordering relationships between remaining nodes.

Clarification of inputs, outputs, and constraints:

• Input: A root node of a BST and an integer key to delete
• Output: The root node of the modified BST (or null if the tree becomes empty)
• Constraints:
  • All node values are unique integers
  • BST property must be maintained: left subtree contains only nodes with values less than the node's value, right subtree contains only nodes with values greater than the node's value
  • Tree can be empty (null root)
  • Key to delete is guaranteed to exist in the tree

Assumptions I am making:

1. The BST is a valid binary search tree with proper ordering
2. The key to delete exists in the tree (as per problem statement)
3. We can modify the input tree structure
4. The solution should maintain BST properties after deletion

Data shape and hidden structure:

The problem involves a binary tree with nodes having:

• val: integer value
• left: reference to left child node
• right: reference to right child node

The hidden structure is that the BST property creates a specific ordering that must be preserved during deletion, which affects how we handle three different cases:

1. Node to delete has no children (leaf node)
2. Node to delete has one child
3. Node to delete has two children (most complex case requiring in-order successor replacement)

This structure suggests we need to think about tree traversal and node reorganization while maintaining the BST invariant.

2. Pattern Recognition

Identifying the most likely pattern or patterns

The most likely pattern is Binary Search Tree (BST) property maintenance combined with tree traversal and node manipulation. This is a classic BST modification problem where we need to preserve the BST ordering property after deletion.

Wording that signals the pattern

• "Delete Node in a BST" - directly indicates we're working with BST structure
• The requirement to "maintain BST properties" signals that we must preserve the ordering invariant where left subtree contains only nodes with values less than the node's value, and right subtree contains only nodes with values greater than the node's value
• The problem asks for deletion of a specific node while maintaining structural integrity

Why this problem fits that pattern

This problem fits the BST pattern because:

1. It operates on a binary tree with specific ordering constraints (BST property)
2. The deletion operation must preserve the BST invariants
3. We need to handle three distinct cases when deleting a node: leaf node, node with one child, and node with two children
4. The solution requires careful handling of pointer reassignment to maintain tree structure

Core insight needed to solve it

The core insight is that when deleting a node with two children, we must replace it with either:

• Its inorder predecessor (maximum value in left subtree), or
• Its inorder successor (minimum value in right subtree)

This replacement maintains the BST property because:

• The inorder predecessor is guaranteed to be less than the node's value (so it can replace it in the left subtree)
• The inorder successor is guaranteed to be greater than the node's value (so it can replace it in the right subtree)
• Both replacements preserve the BST ordering for all other nodes

This approach ensures that after deletion, every node in the left subtree is still less than the root value, and every node in the right subtree is still greater than the root value.

3. Approach Evolution

My first instinct is to solve this using a recursive approach because BST properties naturally lend themselves to recursion - we can leverage the ordering to efficiently locate and delete nodes. But that's O(n²) in worst case for skewed trees because we might need to traverse from root to leaf multiple times, and that's not optimal.

Let me think about how to optimize this. I notice that if I maintain the BST property throughout deletion, I can reduce it to O(h) where h is height of tree. The key insight is that when deleting a node, I have three cases to handle:

1. Node has no children (leaf) - just remove it
2. Node has one child - replace node with its child
3. Node has two children - replace with inorder successor or predecessor

I think the most efficient approach is to find the node to delete and then handle these three cases properly. The key optimization is that when we have two children, instead of copying all values, we can just swap the node's value with its inorder successor and then recursively delete that successor node. This maintains the BST property and keeps the structure clean.

The approach I'll take:

1. First locate the node to delete using BST search property
2. Handle three deletion cases appropriately
3. For case 3, use inorder successor to maintain BST structure
4. Maintain the recursive structure to keep code clean and readable

This approach is O(h) time where h is height of tree, which is optimal for BST deletion. The invariants that must hold are:

• BST property: left subtree < node < right subtree
• Parent-child relationships remain valid after deletion
• The inorder traversal sequence is preserved for the remaining nodes

The algorithm works by leveraging BST's natural ordering to find the target node efficiently, then carefully handling the three deletion scenarios while preserving the tree's structural integrity.

4. Data Structure Choice

For the Delete Node in a BST problem, I'll use the following data structures:

Primary Data Structures:

1. Binary Search Tree Node: The standard TreeNode structure with val, left, and right fields
2. Recursive call stack: Implicitly used for the deletion process - this is the primary mechanism for traversing and modifying the tree

Why Each Data Structure Is Needed:

The TreeNode structure is essential because:

• It represents the fundamental building block of our BST
• It maintains the necessary parent-child relationships for tree traversal
• The BST property (left subtree < node value < right subtree) must be preserved during deletion

The recursive call stack is crucial because:

• It enables us to efficiently navigate to the target node while maintaining the path
• It allows us to handle the three deletion cases (leaf, one child, two children) in a clean recursive manner
• It naturally handles the tree reorganization without requiring explicit stack management

Time and Space Impact:

• Time complexity remains O(h) where h is the height of the tree (O(log n) for balanced trees, O(n) for skewed trees)
• Space complexity is O(h) due to the recursive call stack depth
• No additional space is needed for auxiliary data structures beyond what's required by the tree itself

Helper Structure: No additional helper data structures are needed beyond the standard TreeNode structure. The recursive approach naturally handles all necessary bookkeeping through function parameters and return values.

This choice is optimal because:

1. It leverages the natural recursive structure of BSTs
2. It maintains the BST property without requiring additional validation steps
3. It uses minimal extra space beyond what's necessary for the recursive traversal
4. The solution is clean and readable, which is important in an interview setting

5. Algorithm Walkthrough

Let me trace through the algorithm with a concrete example to demonstrate how it works step-by-step.

Consider BST with nodes: [50, 30, 70, 20, 40, 60, 80] and we want to delete node with value 30.

Step 1: Start at root (50). Target = 30, so we go left to node 30.

• Current node: 50
• Target: 30
• Since 30 < 50, go left

Step 2: Found target node (30). Node 30 has two children (20 and 40).

• Current node: 30
• Node has two children, so we need to find inorder successor

Step 3: Find inorder successor of node 30 (which is rightmost node in left subtree).

• Go to left child of 30: 20
• Go right from 20: null → 20 is the inorder successor

Step 4: Replace value of node 30 with value of inorder successor (20).

• Replace 30 with 20 in the tree structure

Step 5: Delete the inorder successor node (20) from its original position.

• Remove node 20 from tree

Step 6: Update parent references to maintain BST property.

• Parent of 30 (which was 50) now points to 20 instead of 30

The algorithm handles all three cases:

1. Node with no children: Simply remove it
2. Node with one child: Replace node with its child
3. Node with two children: Replace node with inorder successor and remove the successor

Edge cases are handled by checking null conditions and maintaining proper parent-child relationships throughout the deletion process.

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null) return null;
        
        // Step 1: Find the node to delete
        if (key < root.val) {
            root.left = deleteNode(root.left, key);
        } else if (key > root.val) {
            root.right = deleteNode(root.right, key);
        } else {
            // Step 2: Node to delete found
            // Case 1: Node has no children (leaf node)
            if (root.left == null && root.right == null) {
                return null;
            }
            
            // Case 2: Node has only one child
            if (root.left == null) {
                return root.right;
            }
            if (root.right == null) {
                return root.left;
            }
            
            // Case 3: Node has two children
            // Find inorder successor (smallest in right subtree)
            TreeNode successor = findMin(root.right);
            
            // Replace current node's value with successor's value
            root.val = successor.val;
            
            // Delete the successor node from right subtree
            root.right = deleteNode(root.right, successor.val);
        }
        
        return root;
    }
    
    private TreeNode findMin(TreeNode node) {
        while (node.left != null) {
            node = node.left;
        }
        return node;
    }
}

6. Java Solution

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        // Base case: empty tree
        if (root == null) {
            return null;
        }
        
        // If key is smaller, search in left subtree
        if (key < root.val) {
            root.left = deleteNode(root.left, key);
        } 
        // If key is larger, search in right subtree
        else if (key > root.val) {
            root.right = deleteNode(root.right, key);
        } 
        // Found the node to delete
        else {
            // Case 1: Node has no children (leaf node)
            if (root.left == null && root.right == null) {
                return null;
            }
            
            // Case 2: Node has only one child
            if (root.left == null) {
                return root.right;
            }
            if (root.right == null) {
                return root.left;
            }
            
            // Case 3: Node has two children
            // Find the inorder successor (smallest node in right subtree)
            TreeNode successor = findMin(root.right);
            
            // Replace current node's value with successor's value
            root.val = successor.val;
            
            // Delete the successor node from right subtree
            root.right = deleteNode(root.right, successor.val);
        }
        
        return root;
    }
    
    private TreeNode findMin(TreeNode node) {
        // Keep going left until we reach the minimum node
        while (node.left != null) {
            node = node.left;
        }
        return node;
    }
}

This solution implements a recursive approach to delete a node from a Binary Search Tree. The key insight is that when deleting a node with two children, we must maintain the BST property by replacing it with either its inorder predecessor or successor. I chose to use the inorder successor (minimum node in right subtree) as it's more intuitive and maintains the same structure. The solution handles all three cases of node deletion efficiently while preserving the BST property throughout the operation.

7. Complexity Analysis

Time Complexity: O(h) where h is the height of the BST, which translates to O(log n) for a balanced tree and O(n) for a skewed tree.

The algorithm performs at most one path traversal from root to the target node, and then potentially one additional traversal to find the inorder successor (at most one step). Each operation on a single node is O(1), so the overall time complexity is linear in the height of the tree.

Space Complexity: O(h) due to the recursion stack in the worst case (skewed tree), which can grow up to the height of the tree. For a balanced BST, space complexity would be O(log n).

In the iterative approach, we could reduce space to O(1) for the auxiliary space (excluding input), but the recursion stack still requires O(h) space.

The solution is optimal for the BST deletion problem because:

1. We must traverse to find the target node at least once (O(h))
2. We must handle the deletion logic properly, which requires at most one additional traversal to find the inorder successor
3. No better approach exists for general BST deletion that maintains the BST properties

The complexity matches the theoretical lower bound for BST operations, making this solution efficient and optimal for the given constraints.

8. Edge Cases & Pitfalls

Empty and Minimal Inputs

• Empty BST: When root is null, the method should return null without any operation
• Single node BST: When deleting the root node of a single-node tree, we should return null
• Leaf node deletion: Deleting a leaf node requires proper handling of parent references

Duplicate Values and Repeated States

• BST property violation: The problem assumes a valid BST where duplicates are typically stored in the right subtree
• Multiple references to same value: When a node has the same value as the target, we must delete the correct node (typically the first occurrence in in-order traversal)

Boundary Conditions

• Deleting minimum/maximum nodes: These require special handling of the root pointer or parent references
• Target node not found: The method should return the original tree unchanged when the target doesn't exist
• Root node deletion: Special case requiring careful handling of the new root

Common Implementation Mistakes

• Incorrect parent reference updates: Failing to update the parent's left/right pointer when deleting a node
• Missing null checks: Not checking for null children before accessing their properties
• Wrong replacement strategy: Using wrong node as successor in the replacement logic (e.g., using inorder predecessor instead of successor)
• Memory leaks: Not properly setting deleted node's references to null in some implementations
• Inconsistent return values: Returning wrong reference when the root node is deleted vs. when internal nodes are deleted

Implementation-specific Pitfalls

• Modifying input tree: Some implementations incorrectly mutate the original tree structure in ways that break BST properties
• Incorrect successor selection: When replacing with inorder successor, not properly handling the case where successor has a right child
• Missing edge case in successor logic: Not accounting for when the successor is the direct right child of the node to be deleted

9. Alternative Approaches

There are several alternative approaches to deleting a node in a BST, each with different trade-offs:

1. Recursive Approach with Find Successor/Predecessor Instead of copying values, we can recursively find the inorder successor or predecessor and replace the node's value with it. This approach maintains the BST property by swapping values rather than restructuring nodes.

2. Iterative Approach with Stack We can solve this iteratively using a stack to simulate the recursive traversal. This avoids potential stack overflow issues for very deep trees, though it uses O(h) extra space where h is the height.

3. Two-Pointer Approach with Parent Tracking Instead of passing parent references, we could maintain a stack of (node, parent) pairs to track the path. This makes the deletion logic more explicit but increases space complexity.

4. Copy-Value-Then-Delete Strategy This approach copies the value from the successor node and then recursively deletes the successor node. It's conceptually simpler but requires an additional deletion operation.

The chosen solution is preferred because it:

• Uses minimal extra space (O(1) for the main algorithm)
• Maintains clean code structure with clear invariants
• Handles all edge cases explicitly without complex state tracking
• Is more intuitive than the copy-value approach for most developers

The iterative stack-based approach might be preferred in environments with strict recursion limits, but it adds unnecessary complexity for this specific problem. The recursive approach with value swapping is more complex to implement correctly and less readable than the direct node manipulation used in our solution.

10. Test Cases

// Test case 1: Delete leaf node
// Input: root = [5,3,7,2,4,6,8], key = 2
// Expected: [5,3,7,null,4,6,8]
TreeNode root1 = new TreeNode(5);
root1.left = new TreeNode(3);
root1.right = new TreeNode(7);
root1.left.left = new TreeNode(2);
root1.left.right = new TreeNode(4);
root1.right.left = new TreeNode(6);
root1.right.right = new TreeNode(8);
TreeNode result1 = deleteNode(root1, 2);

// Test case 2: Delete node with one child
// Input: root = [5,3,7,2,4,6,8], key = 3
// Expected: [5,4,7,2,null,6,8]
TreeNode root2 = new TreeNode(5);
root2.left = new TreeNode(3);
root2.right = new TreeNode(7);
root2.left.left = new TreeNode(2);
root2.left.right = new TreeNode(4);
root2.right.left = new TreeNode(6);
root2.right.right = new TreeNode(8);
TreeNode result2 = deleteNode(root2, 3);

// Test case 3: Delete root node
// Input: root = [5,3,7,2,4,6,8], key = 5
// Expected: [6,3,7,2,4,null,8] or similar valid BST
TreeNode root3 = new TreeNode(5);
root3.left = new TreeNode(3);
root3.right = new TreeNode(7);
root3.left.left = new TreeNode(2);
root3.left.right = new TreeNode(4);
root3.right.left = new TreeNode(6);
root3.right.right = new TreeNode(8);
TreeNode result3 = deleteNode(root3, 5);

// Test case 4: Delete non-existent node
// Input: root = [5,3,7,2,4,6,8], key = 10
// Expected: [5,3,7,2,4,6,8] (unchanged)
TreeNode root4 = new TreeNode(5);
root4.left = new TreeNode(3);
root4.right = new TreeNode(7);
root4.left.left = new TreeNode(2);
root4.left.right = new TreeNode(4);
root4.right.left = new TreeNode(6);
root4.right.right = new TreeNode(8);
TreeNode result4 = deleteNode(root4, 10);

// Test case 5: Delete node with two children
// Input: root = [5,3,7,2,4,6,8], key = 7
// Expected: [5,3,8,2,4,6,null]
TreeNode root5 = new TreeNode(5);
root5.left = new TreeNode(3);
root5.right = new TreeNode(7);
root5.left.left = new TreeNode(2);
root5.left.right = new TreeNode(4);
root5.right.left = new TreeNode(6);
root5.right.right = new TreeNode(8);
TreeNode result5 = deleteNode(root5, 7);

The test cases cover:

1. Leaf node deletion - Tests the simplest case where a node with no children is removed
2. Node with one child - Tests deletion of a node that has only one child (either left or right)
3. Root node deletion - Tests the special case where the root node is deleted
4. Non-existent key - Tests that the tree remains unchanged when trying to delete a value not present
5. Node with two children - Tests the most complex case where the node to delete has both left and right subtrees

Each test case uses a representative BST structure to validate different deletion scenarios while maintaining the BST property that all left descendants are less than the node and all right descendants are greater.

11. Final Summary

The core idea is to efficiently delete a node from a Binary Search Tree while maintaining the BST property by carefully handling three cases: leaf nodes, nodes with one child, and nodes with two children. The solution works by first locating the target node through BST search, then applying the appropriate deletion strategy that preserves the tree's ordering constraints.

This approach is optimal because it leverages the BST property to achieve O(h) time complexity where h is the tree height, and uses only O(1) extra space for the iterative implementation. The key insight is that when deleting a node with two children, we must replace it with either its inorder predecessor or successor to maintain the BST property, which is efficiently handled by finding the maximum node in the left subtree or minimum node in the right subtree.

The solution is robust and handles all edge cases including empty trees, single nodes, and nodes with no children, making it production-ready for real-world BST operations in systems where maintaining tree structure integrity is critical.