# Leetcode Delete Node in a BST problem solution

In this Leetcode Delete Node in a BST problem solution we have 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.

## Problem solution in Python.

```class Solution:
def deleteNode(self, root: TreeNode, key: int) -> TreeNode:
if not root:
return root
if root.val > key:
root.left = self.deleteNode(root.left, key)
return root
elif root.val < key:
root.right = self.deleteNode(root.right, key)
return root
else: # root.val == key
if not root.right:
return root.left
smInRight = root.right
# Find the smallest node of right subtree of root
# and attach left subtree of root to left of the smallest node in right
while smInRight.left:
smInRight = smInRight.left
smInRight.left = root.left
return root.right
```

## Problem solution in Java.

```public TreeNode deleteNode(TreeNode root, int key) {
if(root == null)
return root;

if(root.val == key){
if(root.right == null)
return root.left;

TreeNode curr = root.right;
while(curr.left != null)
curr = curr.left;
curr.left = root.left;

return root.right;
}else if(root.val < key){
root.right = deleteNode(root.right, key);
}else{
root.left = deleteNode(root.left, key);
}
return root;
}
```

## Problem solution in C++.

```class Solution {
public:
TreeNode * deleteNode(TreeNode*& root, int key) {
if (!root) {
return NULL;
}

if (root->val == key) {
if (root->right) {
TreeNode* nextGt = NULL;
findMin(root->right, nextGt);
swap(root->val, nextGt->val);
root->right = deleteNode(root->right, key);
return root;
}
else {
TreeNode* res = root->left;
delete root;
return res;
}
}
else if (root->val < key) {
root->right = deleteNode(root->right, key);
return root;
}
else if (root->val > key) {
root->left = deleteNode(root->left, key);
return root;
}
else {
return root;
}
}
private:
void findMin(TreeNode* root, TreeNode*& min) {
if(!root){
return;
}

min = root;
while (min && min->left) {
min = min->left;
}
}
};
```