1110. Delete Nodes and Return Forest

📝 Problem Details

• Title: 1110. Delete Nodes and Return Forest
• Link: https://leetcode.com/problems/delete-nodes-and-return-forest/
• Difficulty: Medium
• Tags/Categories: Trees Hashmap DFS

input: root of a binary tree each node has a distinct value between 1-1000 after deleting all nodes with a value in to_delete, we are left with a forest forest ⇒ disjoint union of trees return the roots of the trees in the remaining forest

💡 Explanation of Solution

1. convert to_delete into a HashSet (unordered_set)

   • this allows for O(1) lookup of nodes to delete

2. perform a Postorder DFS traversal on the tree

   • process children first before the current node
   • this ensures that we don’t lost access to child nodes when deleting the current node

3. handling detection

   • if the current node is marked for deletion, add its left and right children (if they exist) to the result vector as new trees
   • return nullptr to the parent, effectively remove this node from the tree

4. handling the root

   • if the root is not deleted, add it to the result forest

⌛ Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(n)

💻 Implementation of Solution

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<TreeNode*> delNodes(TreeNode* root, vector<int>& to_delete) {
        unordered_set<int> toDeleteSet(to_delete.begin(), to_delete.end());
        vector<TreeNode*> result;
        root = dfs(root, toDeleteSet, result);
 
        // if the root is still valid, add it to result
        if(root) result.push_back(root);
        return result;
    }
 
    TreeNode* dfs(TreeNode* node, unordered_set<int>& toDeleteSet, vector<TreeNode*>& result) {
 
        // base case
        if(node == nullptr) return nullptr;
 
        // process children first (postorder traversal)
        node->left = dfs(node->left, toDeleteSet, result);
        node->right = dfs(node->right, toDeleteSet, result);
 
        // process current node
        // if current node should be deleted
        if(toDeleteSet.find(node->val) != toDeleteSet.end()) {
            // if there are valid children, they become new roots
            if(node->left) result.push_back(node->left);
            if(node->right) result.push_back(node->right);
            return nullptr; // change it to null to mark it as deleted
        }
 
        return node;
    }
};