# 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

## answer

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

Link: https://leetcode-cn.com/problems/delete-node-in-a-bst

The copyright belongs to Lingkou Network. For commercial reprints, please contact the official authorization, and for non-commercial reprints, please indicate the source.