My google experience
I received this task in Google telephone interview on 05/06/2020 and I tried to solve it using level order traversal (!?!). I was not able to code everything in
I received this task in Google telephone interview on 05/06/2020 and I tried to solve it using level order traversal (!?!). I was not able to code everything in 40 min. I was able to solve it now using the same approach for 26 min (Anyway the solution is not optimal in both terms of memory and speed) this is the code:\n\n```\nprivate void dfs (TreeNode root, Map<TreeNode, TreeNode> graph) {\n        if (root == null) {\n            return;\n        }\n        if (root.left != null) {\n            graph.put(root.left, root);\n        }\n        if (root.right != null) {\n            graph.put(root.right, root);\n        }\n        dfs(root.left, graph);\n        dfs(root.right, graph);\n    }\n\n    public List<TreeNode> delNodes(TreeNode root, int[] to_delete) {\n        List<TreeNode> result = new ArrayList<>();\n        Map<TreeNode, TreeNode> graph = new HashMap<>();\n        Set<Integer> nodesToDelete = new HashSet<>();\n        for (int i : to_delete) nodesToDelete.add(i);\n        Set<TreeNode> set = new HashSet<>();\n        dfs(root, graph);\n        LinkedList<TreeNode> bfs = new LinkedList<>();\n        bfs.add(root);\n        while(!bfs.isEmpty()) {\n            int size = bfs.size();\n            for (int i = 0; i < size; i++) {\n                TreeNode node = bfs.remove();\n                System.out.println(node.val);\n                if (nodesToDelete.contains(node.val)) {\n                    TreeNode parent = graph.get(node);\n                    if (parent != null) {\n                        if (parent.left != null && parent.left.val == node.val) {\n                            parent.left = null;\n                        } else {\n                            if (parent.right != null) {\n                                parent.right = null;\n                            }\n                        }\n                    }\n                } else {\n                    TreeNode parent = graph.get(node);\n                    if (parent == null || nodesToDelete.contains(parent.val)) {\n                        result.add(node);\n                    }\n                }\n                if (node.left != null) {\n                    bfs.add(node.left);\n                }\n                if (node.right != null) {\n                    bfs.add(node.right);\n                }\n            }\n        }\n        return result;\n    }\n```
[]