[JS] DFS, faster than 99.62%, with explanation
This approach allows for O(n) time (1 pass) and O(log n) extra space.\n\nThe 2 requirements:\n- Delete all nodes whose value \u2208 to_delete.\n- Return the roo
This approach allows for O(n) time (1 pass) and O(log n) extra space.\n\nThe 2 requirements:\n- Delete all nodes whose value \u2208 `to_delete`.\n- Return the roots of the trees in the remaining forest.\n\nOverall, I\'m traversing the forest (from my `roots` set) while deleting the relevant nodes on the fly and (de)populating `roots` as I go.\n\nI\'ll populate `roots` with the existent children of the node that I am about to delete.\n\nDeleting the relevant nodes means deleting the pointer to them; which will either live in their parent\'s node, or in `roots`. Hence I\'ll keep track of a `parent` variable as I go and delete pointers from the relevant source when necessary.\n\n```javascript\nfunction delNodes(root, to_delete) {\n    to_delete = new Set(to_delete);    \n    const roots = new Set([root]);\n    for (const r of roots)\n        dfs(roots, to_delete, r, null);\n    return Array.from(roots);\n}\n\nfunction dfs(roots, to_delete, root, parent) {\n    if (to_delete.has(root.val)) {\n        root.left && roots.add(root.left);\n        root.right && roots.add(root.right);\n        if (!parent) return roots.delete(root);\n        parent[parent.left === root ? \'left\' : \'right\'] = null;\n    }\n    root.left && dfs(roots, to_delete, root.left, root);\n    root.right && dfs(roots, to_delete, root.right, root);\n}\n```
['Depth-First Search', 'JavaScript']