LeetCode 450. Delete Node in a BST

Question

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.

https://leetcode.com/problems/delete-node-in-a-bst/

Solution

• Solution1

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) return root.right;
        else if(root.right == null) return root.left;
        else{
            root.val = findMin(root.right);
            root.right = deleteNode(root.right, root.val);
        }
        return root;
    }
    private int findMin(TreeNode node){
        while(node.left != null) node = node.left;
        return node.val;
    }
}

Complexity:

Time complexity: O(logn)

Space complexity: O(H)