Delete Nodes And Return Forest

Leetcode Problem:

• Delete Nodes And Return Forest

Summary

• Given a binary tree and a list of values to delete, return the roots of the trees in the remaining forest.

Approach

• We use a depth-first search approach to traverse the binary tree
• We first create a vector to store the roots of the trees in the remaining forest
• Then, we iterate over the list of values to delete and for each value, we traverse the binary tree to find and delete the nodes with the given value
• After deleting the nodes, we check if the node has children
• If it does, we add the children to the vector of roots
• Finally, we return the vector of roots.

Complexity

• O(n * m) where n is the number of nodes in the binary tree and m is the number of values to delete.

Explain

• The solution code defines a class Solution with a method delNodes that takes the root of a binary tree and a vector of values to delete as input
• It uses a helper function traversal to delete the nodes with the given values
• The traversal function checks if the current node has the given value and if so, it deletes the node and its children
• If the node does not have the given value, it recursively calls itself on the left and right children of the node
• After deleting the nodes, it checks if the node has children and if so, it adds the children to the vector of roots
• The method returns the vector of roots.

Solution Code:

/**
 * 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:
    bool traversal(TreeNode* ptr, vector &ans, int target){
        if(ptr == nullptr) return false;
        if(ptr->val ==  target){
            for(int i = 0 ; i < ans.size(); i++){
                if (ans[i] == nullptr) continue;
                if (ans[i]->val == target){
                    ans[i] = nullptr;
                    break;
                }
            }
            if (ptr->left){
                ans.push_back(ptr->left);
            }
            if (ptr->right){
                ans.push_back(ptr->right);
            }
            return true;
        }

        if (traversal(ptr->left, ans, target)){
            ptr->left = nullptr;
        }
        if (traversal(ptr->right, ans, target)){
            ptr->right = nullptr;
        }
        return false;
    }
    vector delNodes(TreeNode* root, vector& to_delete) {
        vector ans = {root};
        for(int i = 0 ; i < to_delete.size(); i++){
            for(int j = 0 ; j < ans.size(); j++){
                traversal(ans[j], ans, to_delete[i]);
            }
        }
        vector ans2;
        for(int i = 0 ; i < ans.size(); i++){
            if (ans[i] == nullptr) continue;
            ans2.push_back(ans[i]);
        }
        return ans2;
    }
};