✅💯🔥Explanations No One Will Give You🎓🧠2 Detailed Approaches🎯🔥Extremely Simple And Effective🔥
\n        \n            \n                People tell you the world looks a certain way. Parents tell you how to think. Schools tell you how to think. TV. Relig
<blockquote>\n        <p>\n            <b>\n                People tell you the world looks a certain way. Parents tell you how to think. Schools tell you how to think. TV. Religion. And then at a certain point, if you\u2019re lucky, you realize you can make up your own mind. Nobody sets the rules but you. You can design your own life.\n            </b>        \n        </p>\n        <p>\n            --- Carrie Ann Moss ---\n        </p>\n</blockquote>\n\n# \uD83D\uDC51Problem Explanation and Understanding:\n\n## \uD83C\uDFAF Problem Description\nYou are given a root of a binary tree `root` and an array of integers `to_delete`. You task is to delete every node with value in `to_delete` and then return every root of the forest which was created.\n\n## \uD83D\uDCE5\u2935\uFE0F Input:\n- Root of a binary tree `root`.\n- Integer array `to_delete`\n\n## \uD83D\uDCE4\u2934\uFE0F Output:\nThe array with every root in the forest in any order\n\n---\n\n# 1\uFE0F\u20E3\uD83E\uDDE0 Approach 1: Recursion\n\n# \uD83E\uDD14 Intuition\nThe first way to solve problem I\'ve came up with - recursion, let\'s look at this approach\n- First of all, general for every approach it\'s good to convert `to_delete` into hashset (set) because we are going to check for every node if its value is in `to_delete` and looking for this value in array would be `O(n)` which will be in total `O(n * m)` where n - number of nodes and m - number of nodes to delete, so we convert `to_delete` in the set to have ability to search for element in O(1) time.\n- Let\'s imagine that we\'ve hidden every node in tree except current node, its parent and children. Let\'s think about logic we want to apply for every single node - this is a key to solve almost any recursion problem.\n- For every node we want to do so:\n    - In any case we have to delete this node or not we want to continue our recursion - so we will call recursive function on both our children.\n    - In general this is all we want to do in case this node will be saved. Now let\'s think what we need to do in case when we need to delete this node:\n        - First of all we want to disconnect this node from its parent (so we\'ll pass as parameters to our function parent node and whether current node is left child of parent)\n        - Then, we know that after deleting both our children will be roots for two trees if they exist, but here\'s a problem - what if we already deleted parent node and now looking at child we want to delete too? We just need to delete this node as root from result and add its children - all is simple.\n- In fact, this is whole logic for recursion approach, it\'s not hard to come up with, let\'s make a quick dry run and move on to the code.\n\n<details>\n    <summary>For Dry Run Click Here</summary>\n\n### Input\n```\n       1\n      / \\\n     2   3\n    / \\   \\\n   4   5   6\n```\n\nAnd `to_delete` = [3, 5]\n\n### Dry Run Table\n\n| Step | Node | Action | Parent | isLeft | Resulting Trees (res) | Notes |\n|------|------|--------|--------|--------|-----------------------|-------|\n| 1    | 1    | Visit  | None   | False  | {1: Node(1)}          | Start recursion from root |\n| 2    | 2    | Visit  | 1      | True   | {1: Node(1)}          | Recurse to left child of 1 |\n| 3    | 4    | Visit  | 2      | True   | {1: Node(1)}          | Recurse to left child of 2 |\n| 4    | None | Return | 4      | True   | {1: Node(1)}          | Left child of 4 is None |\n| 5    | None | Return | 4      | False  | {1: Node(1)}          | Right child of 4 is None |\n| 6    | 4    | Done   | 2      | True   | {1: Node(1)}          | 4 is not in to_delete |\n| 7    | 5    | Visit  | 2      | False  | {1: Node(1)}          | Recurse to right child of 2 |\n| 8    | None | Return | 5      | True   | {1: Node(1)}          | Left child of 5 is None |\n| 9    | None | Return | 5      | False  | {1: Node(1)}          | Right child of 5 is None |\n| 10   | 5    | Delete | 2      | False  | {1: Node(1)}          | Remove 5 from the tree, 5 is in to_delete |\n| 11   | 2    | Done   | 1      | True   | {1: Node(1)}          | 2 is not in to_delete |\n| 12   | 3    | Visit  | 1      | False  | {1: Node(1)}          | Recurse to right child of 1 |\n| 13   | None | Return | 3      | True   | {1: Node(1)}          | Left child of 3 is None |\n| 14   | 6    | Visit  | 3      | False  | {1: Node(1)}          | Recurse to right child of 3 |\n| 15   | None | Return | 6      | True   | {1: Node(1)}          | Left child of 6 is None |\n| 16   | None | Return | 6      | False  | {1: Node(1)}          | Right child of 6 is None |\n| 17   | 6    | Done   | 3      | False  | {1: Node(1)} | 6 is not in to_delete, return to parent |\n| 18   | 3    | Delete | 1      | False  | {1: Node(1), 6: Node(6)} | Remove 3 from the tree, 3 is in to_delete and add 6 as new root |\n| 19   | 1    | Done   | None   | False  | {1: Node(1), 6: Node(6)} | 1 is not in to_delete, end recursion |\n\n### Final Result\nThe resulting forest after deleting the nodes [3, 5] would be:\n```\n       1       6\n      /                 \n     2                   \n    /\n   4\n```\n\n**Resulting roots:** `[1, 6]`\n</details>\n\n# \uD83D\uDC69\uD83C\uDFFB\u200D\uD83D\uDCBB Coding \n- Convert `to_delete` list to a set for `O(1)` lookup time.\n- Define a recursive function `recursion` that traverses the tree.\n    - If the current node is `None`, return immediately.\n    - Recurse on the left and right children of the current node.\n    - If the current node\'s value is in `to_delete`:\n        - If the current node is in `res`, delete it from `res`.\n        - Disconnect the current node from its parent.\n        - If the current node has children, add them as new roots to `res`.\n- Start the recursion with the root node.\n- Return the values of `res` which represent the roots of the resulting forest.\n\n# \uD83D\uDCDA Complexity Analysis\n- \u23F0 Time complexity: O(n), since we go through each node exactly once\n- \uD83E\uDDFA Space complexity: O(n), since we use recursion (function call stack) and hashmap `res`\n\n# \uD83D\uDCBB Code\n``` python []\nclass Solution:\n    def delNodes(self, root: Optional[TreeNode], to_delete: list[int]) -> list[TreeNode]:\n        res: dict[int, TreeNode] = {root.val: root}\n        to_delete: set[int] = set(to_delete)\n\n        def recursion(parent: TreeNode | None, cur_node: TreeNode | None, isleft: bool) -> None:\n            nonlocal res\n            if cur_node is None:\n                return\n\n            recursion(cur_node, cur_node.left, True)\n            recursion(cur_node, cur_node.right, False)\n\n            if cur_node.val in to_delete:\n                if cur_node.val in res:\n                    del res[cur_node.val]\n\n                if parent:\n                    if isleft:\n                        parent.left = None\n                    else:\n                        parent.right = None\n\n                if cur_node.left:\n                    res[cur_node.left.val] = cur_node.left\n                if cur_node.right:\n                    res[cur_node.right.val] = cur_node.right\n\n        recursion(None, root, False)\n        return res.values()\n```\n``` C++ []\n\nclass Solution {\npublic:\n    vector<TreeNode*> delNodes(TreeNode* root, vector<int>& to_delete) {\n        unordered_map<int, TreeNode*> res;\n        unordered_set<int> to_delete_set(to_delete.begin(), to_delete.end());\n        res[root->val] = root;\n\n        function<void(TreeNode*, TreeNode*, bool)> recursion = [&](TreeNode* parent, TreeNode* cur_node, bool isleft) {\n            if (cur_node == nullptr) return;\n\n            recursion(cur_node, cur_node->left, true);\n            recursion(cur_node, cur_node->right, false);\n\n            if (to_delete_set.find(cur_node->val) != to_delete_set.end()) {\n                if (res.find(cur_node->val) != res.end()) {\n                    res.erase(cur_node->val);\n                }\n\n                if (parent) {\n                    if (isleft) {\n                        parent->left = nullptr;\n                    } else {\n                        parent->right = nullptr;\n                    }\n                }\n\n                if (cur_node->left) {\n                    res[cur_node->left->val] = cur_node->left;\n                }\n                if (cur_node->right) {\n                    res[cur_node->right->val] = cur_node->right;\n                }\n            }\n        };\n\n        recursion(nullptr, root, false);\n        \n        vector<TreeNode*> result;\n        for (auto& pair : res) {\n            result.push_back(pair.second);\n        }\n        \n        return result;\n    }\n};\n```\n``` JavaScript []\nvar delNodes = function(root, to_delete) {\n    let res = {};\n    let to_delete_set = new Set(to_delete);\n    res[root.val] = root;\n\n    function recursion(parent, cur_node, isleft) {\n        if (cur_node === null) return;\n\n        recursion(cur_node, cur_node.left, true);\n        recursion(cur_node, cur_node.right, false);\n\n        if (to_delete_set.has(cur_node.val)) {\n            delete res[cur_node.val];\n\n            if (parent !== null) {\n                if (isleft) {\n                    parent.left = null;\n                } else {\n                    parent.right = null;\n                }\n            }\n\n            if (cur_node.left !== null) {\n                res[cur_node.left.val] = cur_node.left;\n            }\n            if (cur_node.right !== null) {\n                res[cur_node.right.val] = cur_node.right;\n            }\n        }\n    }\n\n    recursion(null, root, false);\n\n    return Object.values(res);\n};\n```\n``` Java []\nclass Solution {\n    public List<TreeNode> delNodes(TreeNode root, int[] to_delete) {\n        Map<Integer, TreeNode> res = new HashMap<>();\n        Set<Integer> to_delete_set = new HashSet<>();\n        for (int val : to_delete) {\n            to_delete_set.add(val);\n        }\n        res.put(root.val, root);\n\n        recursion(null, root, false, res, to_delete_set);\n\n        return new ArrayList<>(res.values());\n    }\n\n    private void recursion(TreeNode parent, TreeNode cur_node, boolean isleft, Map<Integer, TreeNode> res, Set<Integer> to_delete_set) {\n        if (cur_node == null) return;\n\n        recursion(cur_node, cur_node.left, true, res, to_delete_set);\n        recursion(cur_node, cur_node.right, false, res, to_delete_set);\n\n        if (to_delete_set.contains(cur_node.val)) {\n            res.remove(cur_node.val);\n\n            if (parent != null) {\n                if (isleft) {\n                    parent.left = null;\n                } else {\n                    parent.right = null;\n                }\n            }\n\n            if (cur_node.left != null) {\n                res.put(cur_node.left.val, cur_node.left);\n            }\n            if (cur_node.right != null) {\n                res.put(cur_node.right.val, cur_node.right);\n            }\n        }\n    }\n}\n```\n\n\n# 2\uFE0F\u20E3\uD83D\uDE0E Approach 2: Iterative BFS\n\n# \uD83E\uDD14 Intuition\n- This approach is following quite the same logic as previous, but it\'s a little cleaner. Here is a trick - we won\'t add node at res at all if we know we will delete it after.\n- If we go from top to bottom then with logic above we can not think about `res` at all - all added nodes will be valid roots.\n- Considering the model we want to follow we will use BFS to traverse the tree, other logic is the same as it was in Approach 1, but let\'s make the same dry run but with this approach.\n\n<details>\n    <summary>For Dry Run Click Here</summary>\n\n### Input\n```\n       1\n      / \\\n     2   3\n    / \\   \\\n   4   5   6\n```\n\nAnd `to_delete` = [3, 5]\n\n### Dry Run Table\n\n| Step | Node | Action | Queue          | Resulting Trees (res) | Notes |\n|------|------|--------|----------------|-----------------------|-------|\n| 1    | Init | Init   | [1]            | [1]                   | Initialize `res` with root if not in `to_delete` |\n| 2    | 1    | Visit  | []             | [1]                   | Dequeue 1 |\n| 3    | 1    | Check  | [2]            | [1]                   | Append left child 2 to queue |\n| 4    | 1    | Check  | [2, 3]         | [1]                   | Append right child 3 to queue |\n| 5    | 1    | Disconnect | [2, 3]     | [1]                   | 3 is in `to_delete`, disconnect 3 |\n| 6    | 2    | Visit  | [3]            | [1]                   | Dequeue 2 |\n| 7    | 2    | Check  | [3, 4]         | [1]                   | Append left child 4 to queue |\n| 8    | 2    | Check  | [3, 4, 5]      | [1]                   | Append right child 5 to queue |\n| 9    | 2    | Disconnect | [3, 4]     | [1]                   | 5 is in `to_delete`, disconnect 5 |\n| 10   | 3    | Visit  | [4]            | [1]                   | Dequeue 3 |\n| 11   | 3    | Check  | [4, 6]         | [1]                   | Append right child 6 to queue |\n| 12   | 3    | Delete | [4, 6]         | [1, 6]                | 3 is in `to_delete`, add 6 as new root |\n| 13   | 4    | Visit  | [6]            | [1, 6]                | Dequeue 4 |\n| 14   | 4    | Check  | [6]            | [1, 6]                | 4 has no children |\n| 15   | 5    | Visit  | []             | [1, 6]                | Dequeue 6 |\n| 16   | 6    | Check  | []             | [1, 6]                | 6 has no children |\n\n### Final Result\nThe resulting forest after deleting the nodes [3, 5] would be:\n```\n       1       6\n      /                 \n     2                   \n    /\n   4\n```\n\n**Resulting roots:** `[1, 6]`\n</details>\n\n# \uD83D\uDC69\uD83C\uDFFB\u200D\uD83D\uDCBB Coding \n- Convert `to_delete` list to a set for `O(1)` lookup time.\n- Initialize `res` with the root if it is not in `to_delete`, otherwise an empty list.\n- Use a queue for level-order traversal (BFS).\n- While the queue is not empty, process each node:\n  - Dequeue the current node.\n  - If the current node has a left child:\n    - Append it to the queue.\n    - Disconnect it if its value is in `to_delete`.\n  - If the current node has a right child:\n    - Append it to the queue.\n    - Disconnect it if its value is in `to_delete`.\n  - If the current node\'s value is in `to_delete`:\n    - Add its non-deleted children to `res`.\n- Return the list of remaining tree roots `res`.\n\n# \uD83D\uDCD7 Complexity Analysis\n- \u23F0 Time complexity: O(n), since we go through each node exactly once\n- \uD83E\uDDFA Space complexity: O(n) since we use additional queue `queue`\n\n# \uD83D\uDCBB Code\n``` python []\nclass Solution:\n    def delNodes(self, root: Optional[TreeNode], to_delete: list[int]) -> list[TreeNode]:\n        if not root:\n            return\n\n        to_delete: set[int] = set(to_delete)\n        res: list[TreeNode] = [root] if not root.val in to_delete else []\n        queue: deque[TreeNode] = deque([root])\n\n        while queue:\n            cur_node: TreeNode = queue.popleft()\n\n            if cur_node.left:\n                queue.append(cur_node.left)\n\n                if cur_node.left.val in to_delete:\n                    cur_node.left = None  # disconnect left child if we will delete it\n\n            if cur_node.right:\n                queue.append(cur_node.right)\n\n                if cur_node.right.val in to_delete:\n                    cur_node.right = None\n\n            if cur_node.val in to_delete:  # if we need to delete this node\n                if cur_node.left is not None:  # It\'s None if we need to delete left child too\n                    res.append(cur_node.left)\n                if cur_node.right is not None:\n                    res.append(cur_node.right)\n\n        return res\n```\n``` C++ []\nclass Solution {\npublic:\n    vector<TreeNode*> delNodes(TreeNode* root, vector<int>& to_delete) {\n        if (!root) return {};\n\n        unordered_set<int> to_delete_set(to_delete.begin(), to_delete.end());\n        vector<TreeNode*> result;\n        queue<TreeNode*> q;\n        q.push(root);\n\n        while (!q.empty()) {\n            TreeNode* cur_node = q.front();\n            q.pop();\n\n            if (cur_node->left) {\n                q.push(cur_node->left);\n                if (to_delete_set.count(cur_node->left->val)) {\n                    cur_node->left = nullptr;\n                }\n            }\n\n            if (cur_node->right) {\n                q.push(cur_node->right);\n                if (to_delete_set.count(cur_node->right->val)) {\n                    cur_node->right = nullptr;\n                }\n            }\n\n            if (to_delete_set.count(cur_node->val)) {\n                if (cur_node->left) {\n                    result.push_back(cur_node->left);\n                }\n                if (cur_node->right) {\n                    result.push_back(cur_node->right);\n                }\n            } else if (result.empty()) {\n                result.push_back(cur_node);\n            }\n        }\n\n        return result;\n    }\n};\n```\n``` JavaScript []\nvar delNodes = function(root, to_delete) {\n    if (!root) return [];\n\n    let toDeleteSet = new Set(to_delete);\n    let result = [];\n    let queue = [root];\n\n    while (queue.length > 0) {\n        let curNode = queue.shift();\n\n        if (curNode.left) {\n            queue.push(curNode.left);\n            if (toDeleteSet.has(curNode.left.val)) {\n                curNode.left = null;\n            }\n        }\n\n        if (curNode.right) {\n            queue.push(curNode.right);\n            if (toDeleteSet.has(curNode.right.val)) {\n                curNode.right = null;\n            }\n        }\n\n        if (toDeleteSet.has(curNode.val)) {\n            if (curNode.left) {\n                result.push(curNode.left);\n            }\n            if (curNode.right) {\n                result.push(curNode.right);\n            }\n        } else if (result.length === 0) {\n            result.push(curNode);\n        }\n    }\n\n    return result;\n};\n```\n``` Java []\nclass Solution {\n    public List<TreeNode> delNodes(TreeNode root, int[] to_delete) {\n        List<TreeNode> result = new ArrayList<>();\n        if (root == null) return result;\n\n        Set<Integer> toDeleteSet = new HashSet<>();\n        for (int val : to_delete) {\n            toDeleteSet.add(val);\n        }\n\n        Queue<TreeNode> queue = new LinkedList<>();\n        queue.offer(root);\n\n        while (!queue.isEmpty()) {\n            TreeNode curNode = queue.poll();\n\n            if (curNode.left != null) {\n                queue.offer(curNode.left);\n                if (toDeleteSet.contains(curNode.left.val)) {\n                    curNode.left = null;\n                }\n            }\n\n            if (curNode.right != null) {\n                queue.offer(curNode.right);\n                if (toDeleteSet.contains(curNode.right.val)) {\n                    curNode.right = null;\n                }\n            }\n\n            if (toDeleteSet.contains(curNode.val)) {\n                if (curNode.left != null) {\n                    result.add(curNode.left);\n                }\n                if (curNode.right != null) {\n                    result.add(curNode.right);\n                }\n            } else if (result.isEmpty()) {\n                result.add(curNode);\n            }\n        }\n\n        return result;\n    }\n}\n```\n\n## \uD83D\uDCA1\uD83D\uDCA1\uD83D\uDCA1I encourage you to check out [my profile](https://leetcode.com/heir-of-god/) and [Project-S](https://github.com/Heir-of-God/Project-S) project for detailed explanations and code for different problems (not only Leetcode). Happy coding and learning!\uD83D\uDCDA\n\n### Please consider *upvote*\u2B06\uFE0F\u2B06\uFE0F\u2B06\uFE0F because I try really hard not just to put here my code and rewrite testcase to show that it works but explain you WHY it works and HOW. Thank you\u2764\uFE0F\n\n## If you have any doubts or questions feel free to ask them in comments. I will be glad to help you with understanding\u2764\uFE0F\u2764\uFE0F\u2764\uFE0F\n\n![There is image for upvote](https://assets.leetcode.com/users/images/fde74702-a4f6-4b9f-95f2-65fa9aa79c48_1716995431.3239644.png)\n
['Array', 'Hash Table', 'Tree', 'Depth-First Search', 'Binary Tree', 'Python', 'C++', 'Java', 'Python3', 'JavaScript']