Easy Intuitive (BFS+DFS)|| top->bottom height|| bottom->top height✅ ✅
\n\n# Approach\n> Pre Computations:\n1. First I find the level of each node from bottom.(using dfs)\n2. Then I find the level of each node from the top.(using b
\n\n# Approach\n> **Pre Computations:**\n1. First I find the level of each node from bottom.(using `dfs`)\n2. Then I find the level of each node from the top.(using `bfs` using function `f`)\n3. Now i find the path along the max height using `dfs2`.\n>**Query Processing**:\n   - For each query:\n     - If the node is in the main path, calculate the height based on the second-highest height at that level.\n     - If it\u2019s not on the main path, reduce the height by 1.\n\n# Complexity\n- **Time Complexity**:\n  - `O(n)` for calculating node heights and performing level-order traversal.\n  - Each query takes `O(log n)` due to priority queue operations.\n- **Space Complexity**:\n  - `O(n)` for storing node heights, main path, and levels.\n\n# Code\n```\nclass Solution {\npublic:\n    map<int, int> mp, path;\n    map<int, priority_queue<int>> level;\n    void f(TreeNode* root) {\n        queue<TreeNode*> q;\n        q.push(root);\n        int lvl = 0;\n        while (!q.empty()) {\n            int s = q.size();\n            lvl++;\n            while (s--) {\n                auto it = q.front();\n                q.pop();\n                level[lvl].push(mp[it->val]);\n                if (it->right)\n                    q.push(it->right);\n                if (it->left)\n                    q.push(it->left);\n            }\n        }\n    }\n    int dfs(TreeNode* root) {\n        if (!root)\n            return 0;\n        int left = 0, right = 0;\n        if (root->left)\n            left = dfs(root->left);\n        if (root->right)\n            right = dfs(root->right);\n\n        return mp[root->val] = 1 + max(left, right);\n    }\n    void dfs2(TreeNode* root) {\n        if (!root)\n            return;\n        path[root->val]++;\n        if (root->left && root->right) {\n            if (mp[root->left->val] > mp[root->right->val]) {\n                dfs2(root->left);\n            } else\n                dfs2(root->right);\n        } else if (!root->right) {\n            dfs2(root->left);\n        } else if (!root->left) {\n            dfs2(root->right);\n        }\n    }\n    vector<int> treeQueries(TreeNode* root, vector<int>& queries) {\n        dfs(root);\n        dfs2(root);\n        // for (auto it : mp) {\n        //     cout << it.first << " " << it.second << endl;\n        // }\n        vector<int> ans;\n        int h = mp[root->val];\n        f(root);\n        for (auto it : queries) {\n            int nh = h;\n            if (path.find(it) != path.end()) {\n                // the node removed is from the path of the max height\n                int lvl = h-mp[it]+1;//find the level from top\n                if(level[lvl].size() <= 1){\n                    ans.push_back(h-mp[it]-1);//if not other node on same level\n                }\n                else{\n                    int t = level[lvl].top();\n                    level[lvl].pop();\n                    ans.push_back(lvl+level[lvl].top()-2)\n                    //the new height using the second max. height\n                    level[lvl].push(t);\n                }\n            } else {\n                ans.push_back(nh - 1);\n            }\n        }\n        return ans;\n    }\n};\n```
['Tree', 'Depth-First Search', 'Breadth-First Search', 'Binary Tree', 'C++']