LeetCode : 450. Delete Node in a BST

[congr]

[congr]

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

        if (root.val > key) root.left = deleteNode(root.left, key);
        else if (root.val < key) root.right = deleteNode(root.right, key);
        else { // found
            if (root.right == null && root.left == null) return null;
            else if (root.right == null) return root.left;
            else if (root.left == null) return root.right;
            else { // left && right exist
                root.val = getMin(root.right);                
                root.right = deleteNode(root.right, root.val);
            }
        }

        return root;
    }

    int getMin(TreeNode root) {
        while (root.left != null) root = root.left; // !! root.left != null
        return root.val;
    }
}