C++ || DFS || Two Largest Heights || Intuitive
Intuition\n Describe your first thoughts on how to solve this problem. \nIf we are removing any node at some level, then tree\'s overall height will be determin
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nIf we are removing any node at some level, then tree\'s overall height will be determined by the other nodes at the same level.\n\nNow the problem reduces to 3 cases :\n1. If the largest height node is being removed, then 2nd largest height node will determine the height of the remaining tree\n2. If only one node at that level exists, then height of the tree reduces by the height of that node\n3. In all other cases height does not change\n# Approach\n<!-- Describe your approach to solving the problem. -->\nPrecompute nodeToLevel (maps node to the level it belongs) and levelToHeight (stores top 2 heights and corresponding nodes at every level)\nNow process each query according to the above cases and store the height for every query.\n\n# Complexity\n- Time complexity: $$O(n+q)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(n)$$\n<!-- Add your space complexity here, e.g. $$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), right(right) {}\n * };\n */\nclass Solution {\n    map<int, int> nodeToLevel;\n    map<int, priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>> levelToHeight;\n\n    int fillMap(TreeNode* root, int level = 0) {\n        if (!root) return 0;\n\n        nodeToLevel[root->val] = level;\n\n        int lh = fillMap(root->left, level + 1);\n        int rh = fillMap(root->right, level + 1);\n        \n        int height = max(lh, rh);\n\n        levelToHeight[level].push({height, root->val});\n        if (levelToHeight[level].size() > 2) {\n            levelToHeight[level].pop();\n        }\n\n        return 1+height;\n    }\n\npublic:\n    vector<int> treeQueries(TreeNode* root, vector<int>& queries) {\n        nodeToLevel.clear();\n        levelToHeight.clear();\n        int h = fillMap(root)-1;\n\n        vector<int> ans;\n        for (auto q : queries) {\n            int level = nodeToLevel[q];\n\n            auto pq = levelToHeight[level];\n            auto top2 = pq.top(); pq.pop();\n            auto top1 = pq.empty() ? make_pair(0, -1) :pq.top(); pq.push(top2);\n\n            if (q == top1.second) {\n                ans.push_back(h - top1.first + top2.first);\n            }\n            else if(pq.size()==1 && q == top2.second){\n                ans.push_back(h - top2.first - 1);\n            }\n            else {\n                ans.push_back(h);\n            }\n        }\n\n        return ans;\n    }\n};\nauto speedup = [](){ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); return 0;}();\n```
['Array', 'Tree', 'Depth-First Search', 'Binary Tree', 'C++']