## Algorithm

Problem Name: 450. 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`

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
struct TreeNode* deleteNode(struct TreeNode* root, int key) {
struct TreeNode *p, **pp;
struct TreeNode *a, *b;
pp = &root;
p = *pp;
while (p) {
if (p->val > key) {
pp = &p->left;
} else if (p->val  <  key) {
pp = &p->right;
} else {
break;
}
p = *pp;
}
if (p) {
// found it!
if (!p->right) {
// free(p);
*pp = p->left;
} else if (!p->left) {
// free(p);
*pp = p->right;
} else {
a = p->left;
b = p->right;
// free(p);
*pp = a;
while (a->right) {
a = a->right;
}
a->right = b;
}
}
return root;
}
``````
Copy The Code &

Input

cmd
root = [5,3,6,2,4,null,7], key = 3

Output

cmd
[5,4,6,2,null,null,7]

### #2 Code Example with C++ Programming

```Code - C++ Programming```

``````
/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* deleteNode(TreeNode* root, int key) {
}

void dfs(TreeNode* pre, TreeNode* cur, int key){
if(!cur) return;
cur->val > key ? dfs(cur, cur->left, key) : cur->val  <  key ? dfs(cur, cur->right, key) : helper(pre, cur);
}

void helper(TreeNode* pre, TreeNode* cur){
TreeNode* p = cur->left;
while(p && p->right) p = p->right;
p ? p->right = cur->right : cur->left = cur->right;
cur == pre->left ? pre->left = cur->left : pre->right = cur->left;
}
};

/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* deleteNode(TreeNode* root, int key) {
if (!root) {
return NULL;
}
TreeNode* parent;
TreeNode* node = dfs(root, head, key, parent);
if (!node) {
return root;
}

TreeNode* l = node->left;
TreeNode* r = node->right;
TreeNode* p = r;
while (p && p->left) {
p = p->left;
}
if (!r) {
r = l;
} else if (p) {
p->left = l;
}
if (node == parent->left) {
parent->left = r;
} else {
parent->right = r;
}
}

TreeNode* dfs(TreeNode* cur, TreeNode* pre, int key, TreeNode*& parent) {
if (!cur) {
return NULL;
}
if (cur->val == key) {
parent = pre;
return cur;
}

if (cur->val > key) {
return dfs(cur->left, cur, key, parent);
} else {
return dfs(cur->right, cur, key, parent);
}
}
};
``````
Copy The Code &

Input

cmd
root = [5,3,6,2,4,null,7], key = 3

Output

cmd
[5,4,6,2,null,null,7]

### #3 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public TreeNode deleteNode(TreeNode root, int key) {
if (root == null) {
return null;
}
if (key > root.val) {
root.right = deleteNode(root.right, key);
} else if (key  <  root.val) {
root.left = deleteNode(root.left, key);
} else {
if (root.left == null || root.right == null) {
return root.left == null ? root.right : root.left;
}
TreeNode inorderSuccessor = root.right;
while (inorderSuccessor.left != null) {
inorderSuccessor = inorderSuccessor.left;
}
root.val = inorderSuccessor.val;
root.right = deleteNode(root.right, inorderSuccessor.val);
}
return root;
}
}
``````
Copy The Code &

Input

cmd
root = [5,3,6,2,4,null,7], key = 0

Output

cmd
[5,3,6,2,4,null,7]

### #4 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const deleteNode = function(root, 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
} else {
let smallestRight = root.right
while(smallestRight.left !== null) smallestRight = smallestRight.left
smallestRight.left = root.left
return root.right
}
}

return root
};
``````
Copy The Code &

Input

cmd
root = [5,3,6,2,4,null,7], key = 0

Output

cmd
[5,3,6,2,4,null,7]

### #5 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def deleteNode(self, root, key):
"""
:type root: TreeNode
:type key: int
:rtype: TreeNode
"""
if not root: return
if root.val > key: root.left = self.deleteNode(root.left, key)
elif root.val < key: root.right = self.deleteNode(root.right, key)
else:
if not root.right: return root.left
elif not root.left: return root.right
tmp, mini = root.right, root.right.val
while tmp.left:
tmp, mini = tmp.left, tmp.left.val
root.val, root.right = mini, self.deleteNode(root.right, mini)
return root
``````
Copy The Code &

Input

cmd
root = [], key = 0

Output

cmd
[]

### #6 Code Example with C# Programming

```Code - C# Programming```

``````
namespace LeetCode
{
public class _0450_DeleteNodeInABST
{
public TreeNode DeleteNode(TreeNode root, int key)
{
if (root == null) return null;

if (key > root.val) root.right = DeleteNode(root.right, key);
else if (key  <  root.val) root.left = DeleteNode(root.left, key);
else
{
if (root.left == null && root.right == null)
return null;
else if (root.right != null)
{
root.val = GetSuccessor(root);
root.right = DeleteNode(root.right, root.val);
}
else
{
root.val = GetPredecessor(root);
root.left = DeleteNode(root.left, root.val);
}
}

return root;
}

private int GetSuccessor(TreeNode node)
{
node = node.right;
while (node.left != null)
node = node.left;

return node.val;
}

private int GetPredecessor(TreeNode node)
{
node = node.left;
while (node.right != null)
node = node.right;

return node.val;
}
}
}
``````
Copy The Code &

Input

cmd
root = [], key = 0

Output

cmd
[]