450. Delete A Node In BST

/**

 * 450. Delete Node in a BST

 * Given a root node reference of a BST and a key, delete the node with the given key in the BST.

 * Return the root node reference (possibly updated) of the BST.

 * Basically, the deletion can be divided into two stages:

 * Search for a node to remove.

 * If the node is found, delete the node.

 * Follow up: Can you solve it with time complexity O(height of tree)?

 * 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.

 */

Please see the solution to the code on github here: https://github.com/zcoderz/leetcode/blob/main/src/main/java/binary_search_tree/DeleteNodeInBST.java

Observation: Need to delete a node in BST. This means we will need to traverse the tree until we find the node. If node has null left or right child then its easy, we just replace the node with the non-null child. In case where both the left and right child are not null, we can traverse the right child to find the minimum node on the right side, delete this node and replace the current node’s value with that of the node we just deleted.

The above cases are not straightforward; hence the question is tricky if you haven’t worked on node deletion from a BST before. The main idea that simplifies the code is that as you unwind the recursion you return the node from that traversal. Returning the node makes adjustments in tree for deletion simple to implement.

Logic is:

1. Traverse the tree until you find the node
2. One the node is found, if its right or left child is null, swap left the non-null child with the node.
   1. This is as easy as return the non-null child instead of the node being deleted.
3. When both left and right child are not null
   1. Iterate leftwards on the right child to find node with the smallest value greater than the value being deleted.
   1. Delete that node.
   1. Swap the node’s value which was deleted in ‘b’ with the node’s value whose deletion was originally requested.

Here is the code:

TreeNode deleteNode(TreeNode root, int key) {
    if(root == null) return null; //edge case
    if(root.val == key) { //here is the case where values match
        //case where left or right or both are null, return the non-null child
        if (root.left == null) {
            return root.right;
        }
        if (root.right == null) {
            return root.left;
        }
        //in case where both left and right are not null recurse down to the in order successor
        //delete that node and swap its values with the node to be deleted.
        TreeNode next = root.right;
        while (next.left != null) {
            next = next.left;
        }
        deleteNode(root, next.val);
        root.val = next.val;
        return root;
    } else if (root.val > key && root.left != null) {
        //set the return value to left node so as to set tree structure correctly.
        root.left = deleteNode(root.left, key);
    } else if (root.val < key && root.right != null) {
        root.right = deleteNode(root.right, key);
    }
    return root;
}