Solution in Linear Complexity || Binary Tree 🔥
To analyze the approach, intuition, and complexity of the provided code, let\'s break down the solution step by step:\n\n### Approach and Intuition\n\n1. Mappin
To analyze the approach, intuition, and complexity of the provided code, let\'s break down the solution step by step:\n\n### Approach and Intuition\n\n1. **Mapping Parents:**\n   - The code starts by mapping each node to its parent using the `find_parent` method. This allows easy access to a node\'s parent when performing deletions.\n\n2. **Marking Nodes for Deletion:**\n   - The `to_delete` array is converted into a `List<Integer>` for easier look-up operations.\n\n3. **Deleting Nodes:**\n   - The deletion process is handled by the `delete_node` method, which performs the actual removal of nodes specified in `to_delete`.\n   - If a node is to be deleted, its children (if any) are recursively processed, and the node is detached from its parent.\n   - If a node is not to be deleted, it is added to the result list and processed recursively.\n\n4. **Traversing the Tree:**\n   - The `traverse` method ensures all nodes are visited, and nodes to be deleted are processed correctly.\n\n### Code Complexity\n\n1. **Time Complexity:**\n   - **Mapping Parents:** The `find_parent` method traverses the entire tree once, leading to a time complexity of \\(O(n)\\), where \\(n\\) is the number of nodes in the tree.\n   - **Deletion Process:** Each node is processed in the `delete_node` method, leading to a time complexity of \\(O(n)\\) for traversing and modifying the tree.\n   - **Overall Time Complexity:** Since both the mapping and deletion processes involve a single traversal of the tree, the overall time complexity is \\(O(n)\\).\n\n2. **Space Complexity:**\n   - **Auxiliary Space for Recursion:** The depth of recursion is limited by the height of the tree. In the worst case, this could be \\(O(n)\\) for a skewed tree, but on average, it is \\(O(\\log n)\\) for a balanced tree.\n   - **Storage for Data Structures:** The `map` and `list` structures store references to nodes and integers, respectively. Both require \\(O(n)\\) space.\n   - **Overall Space Complexity:** The space complexity is \\(O(n)\\) due to the storage requirements and potential recursion depth.\n\n### Summary\n\n- **Approach:** The solution first maps each node to its parent, then traverses the tree to delete specified nodes, and finally handles the subtree additions to the result list.\n- **Intuition:** By knowing each node\'s parent, the deletion process becomes straightforward, allowing efficient detachment and reattachment of subtrees.\n- **Complexity:** The overall time and space complexity are both \\(O(n)\\), making the solution efficient for large trees.\n\n\n# Code\n```\n/**\n * Definition for a binary tree node.\n * public class TreeNode {\n *     int val;\n *     TreeNode left;\n *     TreeNode right;\n *     TreeNode() {}\n *     TreeNode(int val) { this.val = val; }\n *     TreeNode(int val, TreeNode left, TreeNode right) {\n *         this.val = val;\n *         this.left = left;\n *         this.right = right;\n *     }\n * }\n */\nclass Solution {\n    public List<TreeNode> delNodes(TreeNode root, int[] to_delete) {\n        List<TreeNode> list = new ArrayList<>();\n        List<Integer> delete = new ArrayList<>();\n        for(int i:to_delete) delete.add(i);\n        HashMap<TreeNode,TreeNode> map = new HashMap<>();\n        map.put(root,null);\n        find_parent(root,map);\n        delete_node(root,delete,list,map);\n        return list; \n    }\n    void traverse(TreeNode node, List<Integer> delete, List<TreeNode> list, HashMap<TreeNode,TreeNode> map){\n\n        if(node==null) return;\n        if(delete.contains(node.val)) delete_node(node, delete, list,  map);\n        else{\n            traverse(node.left,delete,list,map);\n            traverse(node.right,delete,list,map);\n        }\n    }\n    void delete_node(TreeNode node, List<Integer> delete, List<TreeNode> list, HashMap<TreeNode,TreeNode> map){\n        if(node==null) return;\n\n        if(!delete.contains(node.val)) {\n            list.add(node);\n            traverse(node,delete,list,map);\n        }\n        else{\n            TreeNode parent = map.get(node);\n            if(parent!=null && parent.left!=null && parent.left==node) parent.left = null;\n            if(parent!=null && parent.right!=null && parent.right==node) parent.right = null;\n            delete_node(node.left,delete,list,map);\n            delete_node(node.right,delete,list,map);\n        }\n\n\n    }\n    void find_parent(TreeNode node, HashMap<TreeNode,TreeNode> map){\n        if(node==null) return;\n\n        if(node.left!=null) map.put(node.left,node);\n        if(node.right!=null) map.put(node.right,node);\n        find_parent(node.left,map);\n        find_parent(node.right,map);\n    }\n}\n```
['Hash Table', 'Binary Tree', 'Java']