Delete Tree Nodes - Leetcode Solution

Problem Statement: Given the root of a binary tree, and an integer array called "valuesToDelete", delete the nodes of the tree which have values in the "valuesToDelete" array. For each deleted node, its remaining subtree (if any) should be connected to the parent of the deleted node directly.

Example:

Input:

          5
         / \
        3   6
       / \   \
      2   4   7

valuesToDelete = [3, 5]

Output:

          4
         / \
        2   6
           \
            7

Explanation: The first value to be deleted is 3. After deleting the node 3, its parent (node 5) should have node 2 (its left child) and node 4 (its right child) as its only children. Next, we delete node 5. After deleting node 5, node 4 (which was the right child of node 5) becomes the root of the tree and node 6 (which was the right child of node 5) becomes the right child of node 4.

Solution: One way to solve this problem is to use a bottom-up approach. We can start at the leaves of the binary tree and traverse the tree upwards towards the root. At each node, we check if its left and right children need to be deleted. If a child needs to be deleted, we set the corresponding pointer to NULL and return NULL (indicating that this node should be deleted as well). If both children are NULL or have been deleted, we check if the node's value is in the "valuesToDelete" array. If it is, we return NULL. Otherwise, we return the current node pointer.

Algorithm:

1. Create a helper function called deleteNodesHelper, which takes a binary tree node pointer and the "valuesToDelete" array as inputs and returns a binary tree node pointer.
2. Base Case: If the given node pointer is NULL, return NULL.
3. Recursively delete the left subtree of the current node by calling the deleteNodesHelper function with its left child.
4. Recursively delete the right subtree of the current node by calling the deleteNodesHelper function with its right child.
5. Check if the value of the current node is in the "valuesToDelete" array. a. If it is, set the left and right pointers to NULL and return NULL.
6. Otherwise, if both left and right children of the current node are NULL or have been deleted, the current node needs to be deleted as well, so return NULL.
7. Otherwise, return the current node pointer.
8. In the main function, call the deleteNodesHelper function with the root of the binary tree and the "valuesToDelete" array.
9. Return the root of the modified binary tree.

Time Complexity: The time complexity of this solution is O(n), where n is the number of nodes in the binary tree. We visit each node once in a bottom-up manner.

Space Complexity: The space complexity of this solution is O(h), where h is the height of the binary tree. This is the maximum amount of space used by the call stack during the recursive calls. In the worst-case scenario where the tree is completely unbalanced, the height of the binary tree is equal to n, so the space complexity becomes O(n).

Code:

TreeNode* deleteNodesHelper(TreeNode* node, vector<int>& valuesToDelete) {
    if (node == NULL) return NULL;
    
    node->left = deleteNodesHelper(node->left, valuesToDelete);
    node->right = deleteNodesHelper(node->right, valuesToDelete);
    
    if (find(valuesToDelete.begin(), valuesToDelete.end(), node->val) != valuesToDelete.end()) {
        if (node->left) node->left = NULL;
        if (node->right) node->right = NULL;
        return NULL;
    }
    
    if (node->left == NULL && node->right == NULL) return NULL;
    
    return node;
}

TreeNode* deleteNode(TreeNode* root, vector<int>& valuesToDelete) {
    return deleteNodesHelper(root, valuesToDelete);
}

1