Using Precomputed Heights to Efficiently Handle Tree Queries
Intuition\nThe problem requires calculating the height of a binary tree after removing the subtree rooted at a given node for each query. Since each query is in
# Intuition\nThe problem requires calculating the height of a binary tree after removing the subtree rooted at a given node for each query. Since each query is independent, recalculating the height from scratch each time would be inefficient. A better approach is to precompute each node\'s height and store this information in a way that allows us to quickly adjust the height for each query based on the subtree removal.\n\n# Approach\n1. **Calculate Heights and Levels**:\n   - Use a recursive `height` function to calculate the height of each node from the root. \n   - While calculating the height, store each node\u2019s height and level (distance from the root) in a map `mp`.\n   - Another map `mp2` groups nodes by level, associating each level with a list of nodes and their heights.\n\n2. **Precompute Maximum Heights at Each Level**:\n   - For each level, find the two tallest nodes (i.e., nodes with the largest heights). This allows us to quickly adjust the tree\'s height if the subtree of the tallest node at a level is removed.\n\n3. **Process Each Query**:\n   - For each query, find the level of the queried node and retrieve the maximum and second maximum heights at that level.\n   - If the queried node is the tallest node in its level, adjust the tree height by replacing it with the second maximum height.\n   - Otherwise, the tree height remains the same.\n\n4. **Return Results**:\n   - For each query, add the adjusted height to the result list.\n\n# Complexity\n- **Time complexity**:\n  - Calculating heights and levels for each node takes $$O(n)$$ time.\n  - Processing each query by finding the maximum and second maximum height at each level also takes $$O(n)$$ in total.\n  - So, the overall time complexity is $$O(n)$$.\n\n- **Space complexity**:\n  - Storing heights and levels in maps `mp` and `mp2` requires $$O(n)$$ space.\n  - Thus, the space complexity is $$O(n)$$.\n\n# Code\n```cpp []\n/**\n * Definition for a binary tree node.\n * struct TreeNode {\n *     int val;\n *     TreeNode *left;\n *     TreeNode *right;\n *     TreeNode() : val(0), left(nullptr), right(nullptr) {}\n *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}\n *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),\n * right(right) {}\n * };\n */\nclass Solution {\npublic:\n    unordered_map<int, pair<int, int>> mp;\n    unordered_map<int, vector<pair<int, int>>> mp2;\n\n    int height(TreeNode* root, int level = 0) \n    {\n        if (!root)\n            return 0;\n        if (mp.find(root->val) != mp.end())\n            return mp[root->val].first;\n\n        int l = height(root->left, level + 1);\n        int r = height(root->right, level + 1);\n        int curr = 1 + max(l, r);\n\n        mp[root->val] = {curr, level};\n\n        mp2[level].push_back({root->val, curr});\n\n        return curr;\n    }\n    vector<int> treeQueries(TreeNode* root, vector<int>& queries) {\n        int H = height(root) - 1;\n        int m = queries.size();\n\n        vector<int> ans(m, H);\n        for (int i = 0; i < m; i++)\n        {\n            int q = queries[i];\n            int lev = mp[q].second;\n            int maxi = 0;\n            int secondMaxi = 0;\n            for (auto a : mp2[lev]) \n            {\n                if (a.second > maxi) \n                {\n                    secondMaxi = maxi;\n                    maxi = a.second;\n                } \n                else if (a.second > secondMaxi) \n                {\n                    secondMaxi = a.second;\n                }\n            }\n\n            if (maxi == mp[q].first) ans[i] = H - maxi + secondMaxi;\n        }\n\n        return ans;\n    }\n};\n```
['Array', 'Hash Table', 'Depth-First Search', 'Breadth-First Search', 'Recursion', 'Memoization', 'Binary Tree', 'C++']