# Leetcode 450. Deleting Nodes in a Binary Search Tree

## topic

Given a root node root of a binary search tree and a value key, delete the node corresponding to the key in the binary search tree, and keep the properties of the binary search tree unchanged. Returns a reference to the root node of a binary search tree (possibly updated).

Generally speaking, deleting a node can be divided into two steps:

First find the node that needs to be deleted;
If found, delete it.

##### illustrate:

The time complexity of the algorithm is required to be O(h), where h is the height of the tree.

## Example:

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

5
/ \
3   6
/ \   \
2   4   7

Given the value of the node that needs to be deleted is 3, so we first find the 3 node, and then delete it.

A correct answer is [5,4,6,2,null,null,7], As shown below.

5
/ \
4   6
/     \
2       7

Another correct answer is [5,2,6,null,4,null,7].

5
/ \
2   6
\   \
4   7
```

Because it is a binary search tree, we can find the node to be deleted according to the nature of the binary search tree, and we need to record its parent node.
If the node does not exist, no action is required.
If it is the root node,

• If the left subtree is empty, return the right subtree directly
• If the left subtree is not empty, put the right subtree of the root node in the rightmost part of the left subtree

In other cases, it is similar to the previous case, except that the parent node of the deleted node needs to be connected to the node below
See the code for details

## code

```TreeNode* deleteNode(TreeNode* root, int key) {
TreeNode *pre=root,*now = root;
while(now && now->val != key){
pre = now;
if(now->val < key)  now = now->right;
else    now = now->left;
}
if(now == NULL) return root;		//The node was not found
else if(now == root){				//delete the root node
TreeNode* newL = now->left;
if(newL == NULL){				//Return the right subtree directly
if(now->right == NULL)  return nullptr;
else root = now->right;
}else{							//Put the right subtree to the far right of the left subtree
while(newL->right) newL = newL->right;
newL->right = now->right;
root = root->left;
}
}else{
TreeNode* newL = now->left;
if(newL == NULL){			//delete node without left subtree
if(pre->val < key){		//If the parent node of the deleted node is smaller than the deleted node, then the right subtree of the deleted node should be placed on the right subtree of the parent node
if(now->right == NULL)  pre->right = NULL;
else    pre->right = now->right;
}else{				//If the parent node of the deleted node is greater than the deleted node, then the right subtree of the deleted node should be placed on the left subtree of the parent node
if(now->right == NULL)  pre->left = NULL;
else    pre->left = now->right;
}
}else{		//Find the rightmost part of the left subtree first
while(newL->right)  newL = newL->right;
newL->right = now->right;		//Put the right subtree to the rightmost part of the left subtree
if(pre->val < key)  pre->right = now->left;		//If the parent node of the deleted node is smaller than the deleted node, then the root node of the new subtree is on the right subtree of the parent node
else    pre->left = now->left;		//If the parent node of the deleted node is greater than the deleted node, then the root node of the new subtree is on the left subtree of the parent node
}
}
return root;
}
```

Source: LeetCode