Leetcode 450. Delete Nodes in Binary Search Tree C++

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.

Posted by Clukey on Mon, 30 May 2022 12:13:03 +0530