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:

1. Search for a node to remove.
2. If the node is found, delete the node.

Note:Time complexity should be O(height of tree).

Example:

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

    5
   / \
  3   6
 / \   \
2   4   7

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 following BST.

    5
   / \
  4   6
 /     \
2       7

Another valid answer is [5,2,6,null,4,null,7].

    5
   / \
  2   6
   \   \
    4   7

Analysis:

Steps to delete a node in BST:

1. Find the node.
2. Then find largest value on left subtree OR smallest value on the right subtree
3. replace node value with either one and delete the replace node accordingly.

Recursive approach listed below.

Complexity:

Time: O(logn)

Space: O(logn)

Code:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        if(root == null){
            return null;
        }

        if(key < root.val){
            root.left = deleteNode(root.left, key);
        }
        else if(key > root.val){
            root.right = deleteNode(root.right, key);
        }
        else{
            if(root.left == null || root.right == null){
                return root.left == null ? root.right : root.left;
            }
            root.val = findSmallest(root.right);
            root.right = deleteNode(root.right, root.val);
        }
        return root;
    }

    private int findSmallest(TreeNode root)
    {
        return root.left == null ? root.val : findSmallest(root.left);
    }
}