Practice/LinkedIn/Leetcode 450. Delete Node in a BST

Leetcode 450. Delete Node in a BST

CodingMust

Problem

You are given the root of a binary search tree (BST) and an integer key representing the value of a node to delete. Remove the node containing this key from the BST while maintaining the binary search tree property.

After deletion, the resulting tree must still be a valid BST where all nodes in the left subtree are less than the parent, and all nodes in the right subtree are greater than the parent.

Return the root node of the modified BST. If the key is not found in the tree, return the original tree unchanged.

Requirements

1. Maintain the BST property after deletion
2. Handle all three deletion cases: leaf nodes, nodes with one child, and nodes with two children
3. Return the root of the modified tree (which may be different from the original root)
4. If the key doesn't exist in the tree, return the tree unchanged

Constraints

• The number of nodes in the tree is in the range [0, 104]
• -105 ≤= Node.val ≤= 105
• Each node has a unique value
• -105 ≤= key ≤= 105
• Time complexity should be O(h) where h is the height of the tree
• Space complexity should be O(h) for the recursive call stack

Examples

Example 1:

Input: root = [5,3,6,2,4,null,7], key = 3 Output: [5,4,6,2,null,null,7] Explanation: We remove node 3. Since it has two children, we replace it with its inorder successor (smallest node in right subtree), which is 4.

Example 2:

Input: root = [5,3,6,2,4,null,7], key = 0 Output: [5,3,6,2,4,null,7] Explanation: Key 0 doesn't exist in the tree, so no changes are made.

Example 3:

Input: root = [], key = 0 Output: [] Explanation: The tree is empty, so we return null.

Example 4:

Input: root = [5,3,6,2,4,null,7], key = 5 Output: [6,3,7,2,4] Explanation: We remove the root node 5 and replace it with its inorder successor 6.