Delete Node in a BST

Problem Statement

The task is to modify a Binary Search Tree (BST) by deleting a specific node characterized by a given key. The function will be provided a reference to the root node of the BST and the target key to be deleted. Post-deletion, the function should return the root node reference of the potentially modified BST. The operation involves two primary steps: locating the node to be deleted based on the key and, if found, removing it efficiently while ensuring the BST properties are maintained.

Examples

Example 1

Input:

root = [5,3,6,2,4,null,7], key = 3

Output:

[5,4,6,2,null,null,7]

Explanation:

Given key to delete is 3. So we find the node with value 3 and delete it.
One valid answer is [5,4,6,2,null,null,7], shown in the above BST.
Please notice that another valid answer is [5,2,6,null,4,null,7] and it's also accepted.

Example 2

Input:

root = [5,3,6,2,4,null,7], key = 0

Output:

[5,3,6,2,4,null,7]

Explanation:

The tree does not contain a node with value = 0.

Example 3

Input:

root = [], key = 0

Output:

[]

Constraints

• The number of nodes in the tree is in the range [0, 104].
• -105 <= Node.val <= 105
• Each node has a unique value.
• root is a valid binary search tree.
• -105 <= key <= 105

Approach and Intuition

To approach the problem of deleting a node from a BST without compromising the tree's structural and ordering properties, an intuitive step-wise method can be adopted:

1. Search for the Target Node:

   • Traverse the tree starting from the root. Compare the key with the current node's value.
   • If the key is less than the current node’s value, proceed to the left child.
   • If the key is greater, move to the right child.
   • If the key matches the current value, the target node is found.

2. Delete the Node:

   • If the node to be deleted has no children, simply remove the node.
   • If the node has one child, remove the node and link its parent to its child.
   • If the node has two children, find the in-order successor of the node (smallest node in the right subtree), copy its value to the target node, then recursively delete the in-order successor. This maintains the BST properties.

The examples provided illustrate different scenarios:

• Example 1: The node with the value 3 is found and successfully deleted. The BST adjusts by either promoting one of the child nodes or rearranging the nearby nodes to maintain order. Two variations are possible in the final structure, reflecting flexibility in handling two-child deletions.
• Example 2: The given key 0 is not found in the tree, so the tree remains unchanged.
• Example 3: An empty tree scenario, where no action is taken as there are no nodes to search or delete.

Considering the constraints, the solution is expected to handle cases varying from empty trees to trees with a large number of nodes, ensuring robust performance across different scenarios, accounting for the extremities based on the node value limits provided. This approach leverages the properties of BSTs, primarily the ordered nature, to efficiently locate and remove nodes, using recursive strategies for complex deletions involving two children.

Solutions

class Solution {
  public int findSuccessor(TreeNode node) {
    node = node.right;
    while (node.left != null) node = node.left;
    return node.val;
  }
    
  public int findPredecessor(TreeNode node) {
    node = node.left;
    while (node.right != null) node = node.right;
    return node.val;
  }
    
  public TreeNode removeNode(TreeNode node, int key) {
    if (node == null) return null;
    
    if (key > node.val) node.right = removeNode(node.right, key);
    else if (key < node.val) node.left = removeNode(node.left, key);
    else {
      if (node.left == null && node.right == null) node = null;
      else if (node.right != null) {
        node.val = findSuccessor(node);
        node.right = removeNode(node.right, node.val);
      }
      else {
        node.val = findPredecessor(node);
        node.left = removeNode(node.left, node.val);
      }
    }
    return node;
  }
}