EULERIAN TOUR-USE IN PROBLEMS OF SUBTREE REMOVAL
PLEASE UPVOTE IF U FIND MY SOLUTION HELPFUL :)\n\n\n/*\nEULERIAN TOUR: primarily used while handling problems of subtree removal\nmake a tour during performing 
**PLEASE UPVOTE IF U FIND MY SOLUTION HELPFUL :)**\n\n```\n/*\nEULERIAN TOUR: primarily used while handling problems of subtree removal\nmake a tour during performing a dfs traversal and store it\n\nfor a trivial tree: root\n                    /  \\\n                  left right\nthe tour will be:root->left->left->right->right->root\nso every node will appear twice in the tour array once when it is visited for the first time(no left or\nright subtree of it is visited earlier) and the other when it is visited for the last time(when both left and right subtrees are visited)\n\nNOW WHEN A SUBTREE IS REMOVED THE REMAINING TREE THAT WE HAVE WOULD BE THE SUBARRAY BEFORE THE FIRST \nOCCURENCE OF ROOT AND THE SUBARRAY AFTER THE LAST OCCURENCE OF ROOT\n\nNow we will make a prefix-max-height and a suffix-max-height for this tour array and after the removal of\na subtree the resultant maximum height will be max(prefix_max(first occurence ofsubtree- root-1),suffix_max(last occurence ofsubtree- root+1))\n*/\n\nclass Solution {\n    vector<int>tour,mhl,mhr;\n    map<int,int>h,first,last;\n    void dfs(TreeNode* root,int height)\n    {\n        if(!root)return;\n        h[root->val]=height;\n        first[root->val]=tour.size();\n        tour.push_back(root->val);\n        dfs(root->left,height+1);\n        dfs(root->right,height+1);\n        last[root->val]=tour.size();\n        tour.push_back(root->val);\n    }\npublic:\n    vector<int> treeQueries(TreeNode* root, vector<int>& queries) {\n        dfs(root,0);\n        mhl=vector<int>(tour.size());\n        mhr=vector<int>(tour.size());\n        mhl[0]=mhr[tour.size()-1]=h[root->val];\n     \n        for(int i=1;i<tour.size();i++)mhl[i]=max(mhl[i-1],h[tour[i]]);\n        for(int i=tour.size()-2;i>=0;i--)mhr[i]=max(mhr[i+1],h[tour[i]]);\n        vector<int>res;\n        for(int q:queries)\n        {\n            res.push_back(max(mhl[first[q]-1],mhr[last[q]+1]));\n        }\n        return res;\n    }\n};\n```
[]