## Delete Node in a BST

• Time:O(h) = O(\log n)
• Space:O(h) = O(\log n)

## C++

``````class Solution {
public:
TreeNode* deleteNode(TreeNode* root, int key) {
if (!root)
return nullptr;
if (root->val == key) {
if (!root->left)
return root->right;
if (!root->right)
return root->left;
TreeNode* minNode = getMin(root->right);
root->right = deleteNode(root->right, minNode->val);
minNode->left = root->left;
minNode->right = root->right;
root = minNode;
} else if (root->val < key) {
root->right = deleteNode(root->right, key);
} else {  // root->val > key
root->left = deleteNode(root->left, key);
}
return root;
}

private:
TreeNode* getMin(TreeNode* node) {
while (node->left)
node = node->left;
return node;
}
};
``````

## JAVA

``````class Solution {
public TreeNode deleteNode(TreeNode root, int key) {
if (root == null)
return null;
if (root.val == key) {
if (root.left == null)
return root.right;
if (root.right == null)
return root.left;
TreeNode minNode = getMin(root.right);
root.right = deleteNode(root.right, minNode.val);
minNode.left = root.left;
minNode.right = root.right;
root = minNode;
} else if (root.val < key) {
root.right = deleteNode(root.right, key);
} else { // root.val > key
root.left = deleteNode(root.left, key);
}
return root;
}

private TreeNode getMin(TreeNode node) {
while (node.left != null)
node = node.left;
return node;
}
}
``````

## Python

``````class Solution:
def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
if not root:
return None
if root.val == key:
if not root.left:
return root.right
if not root.right:
return root.left
minNode = self._getMin(root.right)
root.right = self.deleteNode(root.right, minNode.val)
minNode.left = root.left
minNode.right = root.right
root = minNode
elif root.val < key:
root.right = self.deleteNode(root.right, key)
else:  # root.val > key
root.left = self.deleteNode(root.left, key)
return root

def _getMin(self, node: Optional[TreeNode]) -> Optional[TreeNode]:
while node.left:
node = node.left
return node
``````