Java DFS O(N) Solution
Complexity\n- Time complexity:\n \nO(N) for adding elements from to_delete to set \nO(N) for tree traversal.\nSo, overall O(N + N) => O(N).\n\n# Code\n\nclass S
# Complexity\n- Time complexity:\n \nO(N) for adding elements from to_delete to set \nO(N) for tree traversal.\nSo, overall O(N + N) => O(N).\n\n# Code\n```\nclass Solution {\n    public List<TreeNode> delNodes(TreeNode root, int[] to_delete) {\n        List<TreeNode> list = new ArrayList<>();\n        Set<Integer> set = new HashSet<>();\n        for (int i = 0; i < to_delete.length; i++) {\n            set.add(to_delete[i]);\n        }\n        if (!set.contains(root.val)) {\n            list.add(root);\n        } else {\n            if (root.left != null && !set.contains(root.left.val)) list.add(root.left);\n            if (root.right != null && !set.contains(root.right.val)) list.add(root.right);\n        }\n        traverseBST(root.left, root, true, list, set);\n        traverseBST(root.right, root, false, list, set);\n        return list;\n    }\n\n    private static void traverseBST(TreeNode node, TreeNode parent, boolean isLeft, List<TreeNode> list, Set<Integer> delete) {\n        if (node == null) return;\n\n        traverseBST(node.left, node, true, list, delete);\n        traverseBST(node.right, node, false, list, delete);\n\n        if (delete.contains(node.val)) {\n            delete.remove(node.val);\n            if (isLeft) {\n                parent.left = null;\n            } else {\n                parent.right = null;\n            }\n            if (node.left != null) list.add(node.left);\n            if (node.right != null) list.add(node.right);\n        }\n    }\n}\n```
['Java']