Here, We see Delete Node in a BST LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.
List of all LeetCode Solution
Delete Node in a BST LeetCode Solution
Table of Contents
Problem Statement
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:
- Search for a node to remove.
- 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: []
Delete Node in a BST LeetCode Solution C++
class Solution {
public:
TreeNode* deleteNode(TreeNode* root, int key) {
if(root)
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 && !root->right) return NULL;
if (!root->left || !root->right)
return root->left ? root->left : root->right;
TreeNode* temp = root->left;
while(temp->right != NULL) temp = temp->right;
root->val = temp->val;
root->left = deleteNode(root->left, temp->val);
}
return root;
}
};
Code language: C++ (cpp)
Delete Node in a BST LeetCode Solution Java
class Solution {
public TreeNode deleteNode(TreeNode root, int key) {
if(root==null) return null;
if(key<root.val){
root.left = deleteNode(root.left,key);
return root;
}
else if(key>root.val){
root.right = deleteNode(root.right,key);
return root;
}
else{
if(root.left==null){
return root.right;
}
else if(root.right==null){
return root.left;
}
else{
TreeNode min = root.right;
while(min.left!=null){
min = min.left;
}
root.val = min.val;
root.right = deleteNode(root.right,min.val);
return root;
}
}
}
}
Code language: Java (java)
Delete Node in a BST LeetCode Solution JavaScript
var deleteNode = function(root, key) {
if (null === root) { return null; }
if (root.val === key) {
if (null === root.left && null === root.right) { return null; }
if (null !== root.left && null !== root.right) {
let curr = root.right;
while (curr.left) { curr = curr.left; }
curr.left = root.left;
return root.right;
}
if (null === root.left) { return root.right; }
if (null === root.right) { return root.left; }
}
if (key < root.val) {
root.left = deleteNode(root.left, key);
} else {
root.right = deleteNode(root.right, key);
}
return root;
};
Code language: JavaScript (javascript)
Delete Node in a BST LeetCode Solution Python
class Solution(object):
def deleteNode(self, root, key):
if not root: return None
if root.val == key:
if root.left:
left_right_most = root.left
while left_right_most.right:
left_right_most = left_right_most.right
left_right_most.right = root.right
return root.left
else:
return root.right
elif root.val > key:
root.left = self.deleteNode(root.left, key)
else:
root.right = self.deleteNode(root.right, key)
return root
Code language: Python (python)