Java Solution for Height of Binary Tree After Subtree Removal Queries Problem
Intuition\n Describe your first thoughts on how to solve this problem. \nThe goal is to determine the maximum height of the tree after hypothetically removing t
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe goal is to determine the maximum height of the tree after hypothetically removing the subtree rooted at each queried node. Calculating this efficiently for a large number of nodes requires precomputing information about the structure of the tree so that we avoid repeated traversals\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1.\tDFS Traversal for Heights and Depths: Perform a DFS traversal of the tree to calculate the height and depth of each node. For each node:\n\t\u2022\tStore its depth and height in maps for fast access during query processing.\n2.\tStore Maximum Heights by Depth: To efficiently determine the maximum height after removing a subtree rooted at a specific node:\n\t\u2022\tStore the two highest heights of nodes at each depth level in a map. This enables us to quickly find the maximum height for a level after removing a node.\n3.\tAnswer Each Query Efficiently: For each query (removal of a subtree rooted at a specific node):\n\t\u2022\tLook up the depth and height of the node to be \u201Cremoved.\u201D\n\t\u2022\tCheck the heights at that depth level using the precomputed values. If the height of the queried node is the highest, use the second-highest height as the new maximum; otherwise, use the current highest height.\n\t\u2022\tThis results in an efficient, constant-time computation per query.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n1.\tDFS Traversal for Heights and Depths: O(n), where n is the number of nodes, since each node is visited once.\n2.\tBuilding Depth Heights Map: O(n log n), as we sort the list of heights at each depth level. In the worst case, we would sort n nodes in total.\n3.\tQuery Processing: O(q), where q is the number of queries, since each query is processed in constant time by accessing precomputed information.\n\nTotal Time Complexity: O(n log n + q)\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n1.\tHeights and Depths Maps: O(n), as we store depth and height for each node.\n2.\tDepth Heights Map: O(n), as each node\u2019s height is stored in the list corresponding to its depth.\n3.\tResult Array for Queries: O(q), where q is the number of queries.\n\nTotal Space Complexity: O(n + q)\n\n# Code\n```java []\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    private Map<Integer, Integer> heights = new HashMap<>(); \n    private Map<Integer, Integer> depths = new HashMap<>(); \n    private Map<Integer, List<Integer>> depthHeights = new HashMap<>();\n    public int[] treeQueries(TreeNode root, int[] queries) {\n        calculateHeightAndDepth(root, 0);\n\n        for (Map.Entry<Integer, Integer> entry : heights.entrySet()) {\n            int nodeValue = entry.getKey();\n            int height = entry.getValue();\n            int depth = depths.get(nodeValue);\n            depthHeights.computeIfAbsent(depth, k -> new ArrayList<>()).add(height);\n        }\n        for (List<Integer> heightList : depthHeights.values()) {\n            Collections.sort(heightList, Collections.reverseOrder());\n        }\n\n        int[] result = new int[queries.length];\n        \n        for (int i = 0; i < queries.length; i++) {\n            int nodeValue = queries[i];\n            int depth = depths.get(nodeValue);\n            int nodeHeight = heights.get(nodeValue);\n            List<Integer> heightList = depthHeights.get(depth);\n            \n            int maxHeightWithoutNode;\n            if (heightList.size() == 1) {\n                maxHeightWithoutNode = depth - 1;\n            } else if (heightList.get(0) == nodeHeight) {\n                maxHeightWithoutNode = depth + heightList.get(1);\n            } else {\n                maxHeightWithoutNode = depth + heightList.get(0);\n            }\n\n            result[i] = maxHeightWithoutNode;\n        }\n\n        return result;\n    }\n\n    private int calculateHeightAndDepth(TreeNode node, int depth) {\n        if (node == null) return -1;\n\n        depths.put(node.val, depth);\n        int leftHeight = calculateHeightAndDepth(node.left, depth + 1);\n        int rightHeight = calculateHeightAndDepth(node.right, depth + 1);\n\n        int height = 1 + Math.max(leftHeight, rightHeight);\n        heights.put(node.val, height);\n\n        return height;\n    }\n}\n```
['Java']