Simple Approach | Without tree flattening
Intuition\nThink in terms of levels - what could be done if we remove a particular subtree?\n\n# Approach\n1. We can precompute the heights of each subtree root
# Intuition\nThink in terms of levels - what could be done if we remove a particular subtree?\n\n# Approach\n1. We can precompute the heights of each subtree rooted at every node and store them in a vector or array, where the ith element represents the height of the subtree rooted at the ith node.\n   \n2. Maintain a map of vectors to store nodes present at each level, where each level contains a vector of nodes present in that level.\n\n3. Create a map that associates each node with its level, allowing easy lookup of the level for any given node.\n\n4. a. If any node at a specific level has a subtree height greater than the subtree height of the given node, the height of the entire tree remains unchanged.\n\n   b. If the given node has the maximum subtree height at that level, find the second highest subtree height in that level. Subtract the difference between these heights from the original tree height to get the updated height.\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 {\npublic:\n    unordered_map<int,vector<int>>m; // level , node values\n    unordered_map<int,int>levelMap; // value , level\n    vector<int>h;\n    int heightOfSubTree(TreeNode*root,int level){\n        if(root==NULL)return 0;\n\n        int l=0,r=0;\n        l=heightOfSubTree(root->left,level+1);\n        r=heightOfSubTree(root->right,level+1);\n\n        m[level].push_back(root->val);\n        levelMap[root->val]=level;\n        h[root->val]=max(l,r)+1;\n\n        return h[root->val];\n    }\n    vector<int> treeQueries(TreeNode* root, vector<int>& q) {\n        h.assign(1e5+1,0); // height of sub tree\n\n        heightOfSubTree(root,0);\n\n        vector<int>ans;\n\n        for(int i=0;i<q.size();i++){\n            int val=q[i];\n            int l=levelMap[val];\n            int mini=h[val];\n            for(int i=0;i<m[l].size();i++){\n                if(val!=m[l][i]){\n                    if(h[m[l][i]]>=h[val]){\n                        mini=0;\n                        break;\n                    }\n                    else mini=min(mini,h[val]-h[m[l][i]]);\n                }\n            }\n            ans.push_back(h[root->val]-1-mini);\n        }\n\n        return ans;\n\n    }\n};\n```
['C++']