Delete Nodes and Return Forest - C++ || Easy Intutive solution with Detailed explanations
Observations\n If we are standing at some node say a and if we need to delete it, then its child will be separated as new root nodes.\n For example consider bel
# Observations\n* If we are standing at some node say `a` and if we need to delete it, then its child will be separated as new root nodes.\n* For example consider below tree, with `to_delete = [2, 3]`\n    ![image.png](https://assets.leetcode.com/users/images/d0ba647a-351e-4bfc-95c7-2b55ae266e69_1671883982.710551.png)\nIn this case once nodes `2` and `3` are deleted there children nodes will be part of new sub tree.\n\n* Hence keeping above observation in mind we can develop our solution\uD83D\uDE00.\n\n# Function Explanations\n\nHere performing **post-order** tree traversal so that deleting node do not affect the result.\nAs we observe we created the separate sub trees for children and deleted the node which is presnt in `to_delete`\n\n```\nvoid traverse(TreeNode* &root, unordered_set<int> &st, vector<TreeNode*> &res)\n{\n    if(root==NULL) return;\n\n    traverse(root->left, st, res);\n    traverse(root->right, st, res);\n\n    if(st.count(root->val))\n    {\n        if(root->left and !st.count(root->left->val))\n        {\n            res.push_back(root->left);\n        }\n        if(root->right and !st.count(root->right->val))\n        {\n            res.push_back(root->right);\n        }\n        deleteNode(root, st);\n    }\n}\n```\n\nHere performing **pre-order** tree traversal and once we find a node present in `to_delete` we mark such node as `NULL`.\n```\nvoid deleteNode(TreeNode* &root, unordered_set<int> &st)\n{\n    if(root==NULL)\n    return;\n    if(st.count(root->val))\n    {\n        root = NULL;\n        return;\n    }\n}\n```\n\n# Complexity\n- Time complexity: $$O(n)$$ *considering all traversals*\n<!-- Add your time complexity here, e.g.  -->\n\n- Space complexity: $$O(n)$$ *for both recursions stack space and the `unordered_set`*\n<!-- Add your space complexity here, e.g.  -->\n\n# Code\n```\n/**\n * Definition for a binary tree node.\n * struct TreeNode {\n *     int val;\n *     TreeNode *left;\n *     TreeNode *right;\n *     TreeNode() : val(0), left(nullptr), right(nullptr) {}\n *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}\n *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}\n * };\n */\n\nclass Solution {\n\n    void deleteNode(TreeNode* &root, unordered_set<int> &st)\n    {\n        if(root==NULL)\n        return;\n        if(st.count(root->val))\n        {\n            root = NULL;\n            return;\n        }\n    }\n\n    void traverse(TreeNode* &root, unordered_set<int> &st, vector<TreeNode*> &res)\n    {\n        if(root==NULL) return;\n\n        traverse(root->left, st, res);\n        traverse(root->right, st, res);\n\n        if(st.count(root->val))\n        {\n            if(root->left and !st.count(root->left->val))\n            {\n                res.push_back(root->left);\n            }\n            if(root->right and !st.count(root->right->val))\n            {\n                res.push_back(root->right);\n            }\n            deleteNode(root, st);\n        }\n    }\n\npublic:\n\n    vector<TreeNode*> delNodes(TreeNode* root, vector<int>& to_delete) {\n        if(!root) return {};\n        unordered_set<int> st(to_delete.begin(), to_delete.end()); // set created to know in O(1) time whether to deletr or current node\n        vector<TreeNode*> res;\n\n        traverse(root, st, res);\n        deleteNode(root, st); \n\n        if(root)\n        res.push_back(root); // finally adding root node to cover remaing nodes above the nodes to be deleted.\n\n        return res;\n    }\n\n};\n```\n\n# Key Take Aways \uD83D\uDCA1\n* `root` node is passed by reference so that deleting nodes also reflects in original tree in run time.\n\n### Please Upvote if find helpfull\uD83D\uDE04 it means a lot\uD83D\uDCAF.
['Tree', 'Depth-First Search', 'Binary Tree', 'C++']