304 North Cardinal St.
Dorchester Center, MA 02124

# Delete Node in a BST LeetCode Solution

## Problem – 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 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.

Example 1:

``````Input: root = [5,3,6,2,4,null,7], key = 3
Output: [5,4,6,2,null,null,7]
Explanation: Given key to delete is 3. So we find the node with value 3 and delete it.
One valid answer is [5,4,6,2,null,null,7], shown in the above BST.
Please notice that another valid answer is [5,2,6,null,4,null,7] and it's also accepted.``````

Example 2:

``````Input: root = [5,3,6,2,4,null,7], key = 0
Output: [5,3,6,2,4,null,7]
Explanation: The tree does not contain a node with value = 0.``````

Example 3:

``````Input: root = [], key = 0
Output: []``````

Constraints:

• The number of nodes in the tree is in the range `[0, 104]`.
• `-105 <= Node.val <= 105`
• Each node has a unique value.
• `root` is a valid binary search tree.
• `-105 <= key <= 105`

### Delete Node in a BST LeetCode Solution in Java

``````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;
}

TreeNode minNode = findMin(root.right);
root.val = minNode.val;
root.right = deleteNode(root.right, root.val);
}
return root;
}

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

### Delete Node in a BST LeetCode Solution in C++

``````class Solution {
public:
TreeNode* deleteNode(TreeNode* root, int key) {
if(root)
if(key < root->val) root->left = deleteNode(root->left, key);     //We frecursively call the function until we find the target node
else if(key > root->val) root->right = deleteNode(root->right, key);
else{
if(!root->left && !root->right) return NULL;          //No child condition
if (!root->left || !root->right)
return root->left ? root->left : root->right;    //One child contion -> replace the node with it's child
//Two child condition
TreeNode* temp = root->left;                        //(or) TreeNode *temp = root->right;
while(temp->right != NULL) temp = temp->right;     //      while(temp->left != NULL) temp = temp->left;
root->val = temp->val;                            //       root->val = temp->val;
root->left = deleteNode(root->left, temp->val);  //        root->right = deleteNode(root->right, temp);
}
return root;
}
};
``````

### Delete Node in a BST LeetCode Solution in Python

``````class Solution(object):
def deleteNode(self, root, key):
if not root: return None

if root.val == key:
if not root.right: return root.left

if not root.left: return root.right

if root.left and root.right:
temp = root.right
while temp.left: temp = temp.left
root.val = temp.val
root.right = self.deleteNode(root.right, root.val)

elif root.val > key:
root.left = self.deleteNode(root.left, key)
else:
root.right = self.deleteNode(root.right, key)

return root
``````
##### Delete Node in a BST LeetCode Solution Review:

In our experience, we suggest you solve this Delete Node in a BST LeetCode Solution and gain some new skills from Professionals completely free and we assure you will be worth it.

If you are stuck anywhere between any coding problem, just visit Queslers to get the Delete Node in a BST LeetCode Solution

Find on LeetCode

##### Conclusion:

I hope this Delete Node in a BST LeetCode Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.

This Problem is intended for audiences of all experiences who are interested in learning about Data Science in a business context; there are no prerequisites.

Keep Learning!

More Coding Solutions >>

LeetCode Solutions

Hacker Rank Solutions

CodeChef Solutions