450. Delete Node in a BST

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: []

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

Intuition

Approach:

Take Leftmost and join to rightmost

Links

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

Video Links

https://www.youtube.com/watch?v=kouxiP_H5WE&ab_channel=takeUforward

Approach 1:

C++

class Solution {
public:
    TreeNode* find_right(TreeNode* root){
        TreeNode *temp = root;
        while(temp->right){
            temp = temp->right;
        }

        return temp;
    }

    TreeNode* helper(TreeNode* root){
        if(!root->left)
            return root->right;
        else if(!root->right)
            return root->left;

        TreeNode* left_child_root = root->left;
        TreeNode* extreme_right = find_right(left_child_root);
        extreme_right->right = root->right;

        return left_child_root;
    }

    TreeNode* deleteNode(TreeNode* root, int key) {
        if(root == nullptr)
            return root;

        if(root->val == key){
            return helper(root);
        }

        TreeNode *prev = root;
        while(root){
            if(root->val > key){
                if(root->left and root->left->val == key){
                    root->left = helper(root->left);
                    break;
                }
                else{
                    root = root->left;
                }
            }
            else{
                if(root->right and root->right->val == key){
                    root->right = helper(root->right);
                    break;
                }
                else{
                    root = root->right;
                }
            }
        }

        return prev;
    }
};

Approach 2:

C++

Approach 3:

C++

Approach 4:

C++