algoadvance

Leetcode 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.

Clarifying Questions

  1. Question: What should be done if the key is not found in the BST?
    • Answer: If the key is not found, the BST should remain unchanged and should return the root of the BST as is.
  2. Question: Can the BST contain duplicate values?
    • Answer: No, according to the problem definition of a typical BST, all keys are unique.
  3. Question: What are the constraints on the number of nodes in the tree?
    • Answer: The number of nodes in the tree will range from 0 to 10^4.

Strategy

  1. Find the Node: Start from the root and use the BST property to locate the node to be deleted.
  2. Delete the Node with three cases:
    • Case 1: The node to be deleted is a leaf node.
    • Case 2: The node to be deleted has only one child.
    • Case 3: The node to be deleted has two children. Find the inorder successor (smallest node in the right subtree) to replace the node to be deleted, and then delete the inorder successor.
  3. Rebalance: Ensure the BST properties are maintained and return the possibly updated root.

Code

Here is the C++ code to solve the problem:

#include <iostream>

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 root;

        if (key < root->val) {
            root->left = deleteNode(root->left, key);
        } else if (key > root->val) {
            root->right = deleteNode(root->right, key);
        } else {
            // Node with only one child or no child
            if (!root->left) {
                TreeNode* temp = root->right;
                delete root;
                return temp;
            } else if (!root->right) {
                TreeNode* temp = root->left;
                delete root;
                return temp;
            }

            // Node with two children: Get the inorder successor (smallest in the right subtree)
            TreeNode* temp = minValueNode(root->right);
            root->val = temp->val;
            root->right = deleteNode(root->right, temp->val);
        }
        return root;
    }

private:
    TreeNode* minValueNode(TreeNode* node) {
        TreeNode* current = node;
        while (current && current->left) {
            current = current->left;
        }
        return current;
    }
};

int main() {
    Solution solution;
    // Example usage:
    // Constructing a BST
    TreeNode* root = new TreeNode(5);
    root->left = new TreeNode(3);
    root->right = new TreeNode(6);
    root->left->left = new TreeNode(2);
    root->left->right = new TreeNode(4);
    root->right->right = new TreeNode(7);

    // Deleting a node
    int key = 3;
    root = solution.deleteNode(root, key);

    std::cout << "Root after deletion: " << root->val << std::endl; // Expected output root node value

    // Clean up memory
    // Proper tree deletion code should be added here to handle resources.
    return 0;
}

Time Complexity

Explanation

  1. Finding the Node: Use typical BST search.
  2. Deleting the Node: Consider three cases depending on the structure.
  3. Rebalancing: Ensure the BST properties hold after removal by using appropriate successor/predecessor replacement.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI