Trees - 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 of the (modified) BST.

Input: root=[5,3,6,2,4,null,7], key=3 → Output: [5,4,6,2,null,null,7]

Input: root=[5,3,6,2,4,null,7], key=0 → Output: [5,3,6,2,4,null,7]

Three cases for deletion: (1) node has no children — just remove; (2) node has one child — replace with that child; (3) node has two children — replace with the inorder successor (smallest in right subtree) and delete successor.

Search for the key recursively.
If key < root.val: root.left = delete(root.left, key).
If key > root.val: root.right = delete(root.right, key).
If key == root.val: if no left child return right; if no right child return left; else find min in right subtree, set root.val = min.val, delete min from right subtree.

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; if (root.right == null) return root.left; TreeNode min = root.right; while (min.left != null) min = min.left; root.val = min.val; root.right = deleteNode(root.right, min.val); } return root; } }

Time Complexity: O(H) where H is height; O(log N) for balanced BST
Space Complexity: O(H) recursion stack