Think from scratch to optimised solution ||c++
the first thing is it involves removal so segment tree can be implimented?\nbut the thing is if tree is branched it works well bcz updatation in segment tree co
the first thing is it involves removal so segment tree can be implimented?\nbut the thing is if tree is branched it works well bcz updatation in segment tree cost = hight of tree \nbut in worst case it may happen that tree is like a linkedlist so hight = no of nodes so it will fail for \nqueries of order of 10^4\n\n\nin segment tree we will use inorder indexing to figur out the node which need to removed is on the left or right side of current root it will help to get new hight in O(h) complexcity \n\n**Intutive but failed Approach \uD83D\uDE42**\n//using segment tree to find affected branch and then recalculate the hight \n``` complexcity for each query = O(h)  ```\n```\nclass Solution {\npublic:\n    \n    unordered_map<int,int> m;\n    int t=0;\n    unordered_map<TreeNode*,int> seg;\n    int update(TreeNode* root, int tg)  // tg here is index of root to be removed from inorder traversal\n    {\n        if(m[root->val]==tg)  // node to be removed is found  \n        {\n            // seg[idx]=0;\n            return 0; // return 0 as this is removed so no contribution from this subtree\n        }\n        if(m[root->val]<tg)// if target node is on the right side\n        {\n            int r=update(root->right, tg); // we only need to check right side as left side is uneffected same for left side as well\n            \n            int l=0;\n            if(root->left) l=seg[root->left];\n            return max(l,r)+1;\n        }\n        else  // if target node is on left side \n        {\n\t\t   \n            int l=update(root->left,tg);\n            int r=0;\n            if(root->right) r=seg[root->right];\n            return max(l,r)+1;\n        }\n        \n    }\n\t\n    int solve(TreeNode* root) // for inorder indexing and intialisation of segment tree\n    {\n        if(root==NULL) return 0;\n     \n        int l=solve(root->left);\n        m[root->val] =t; t++;\n        int r= solve(root->right);\n        return seg[root]=max(l,r)+1;\n    }\n    \n    vector<int> treeQueries(TreeNode* root, vector<int>& q) \n    {\n        solve(root);\n        vector<int> ans;\n        for(auto i: q)\n        {\n            ans.push_back(update(root,m[i])-1);\n        }\n        return ans;\n        \n    }\n};\n```\n\n```\n37 / 40 test cases passed.\n```\n\n**Optimised approach** \n\nto get rid of this one sided branched tree which fails segment tree idea bcz the hight is same as no of nodes \nso now we can think some thing about in & out time\n\nany root node will have lesser in time and higher out time than any of it bellow child nodes till leaf node why? bcz u enter from root so let\'s say in time is t then u keep increment timer when u go for childs so when u go for left timer is t+1 and so on.... so ``` intime of root is always smaller than child ``` \n\nand similarly when u leave from child and go to parent u incrment timer so ``` parent node (root ) ``` will have always ``` more out time  ``` than any of it ``` child node ```\n\nwe store all nodes on hight basis like level oreder traversal  hight is 0 at root node and increses by +1 as we move down \nhere insted of storing nodes we store inout time of those nodes in sorted order \nso now if we need to remove any root we will take it\'s ``` intime and out time values ``` and apply a binary search on hight (it works bcz intime  increases& out time decreases down the tree ) and we check is their any node at hight h such that ```  it\'s intime is less that root  or out time more than this root ``` this means their is atlease one branch which is not a child branch of our root (which is going to be removed) has atleast a node on this hight ``` ( so our hight is ovisly >=h ) ``` so we can now go down  or if their is no such node then we need to go up side using binary search method\n\n\n\n\n```\n\n\nusing pii = pair<int,int>;\n\nclass Solution {\npublic:\n    // in out time pairs at particular depth\n    vector<pii> g[100005];\n    \n    int in[100005];\n    int out[100005];\n    int timer = 0;\n    \n    // Max Depth Overall\n    int mx;\n\n    \n    // Calculating in out times for each vertex\n    // postorder assignment\n    void dfs(TreeNode* root, int depth)\n    {\n        if(root == nullptr)return;\n        \n        in[root -> val] = timer++;\n\n        dfs(root -> left,depth + 1);\n        dfs(root -> right, depth + 1);\n\n        out[root -> val] = timer++;\n\n        g[depth].push_back({in[root -> val], out[root -> val]});\n        mx = max(mx,depth);\n    }\n\n    // check for particular height\n    int check(int mid, int src)\n    {\n        if(g[mid].size() == 0) return 0;\n\n        // check if first vertex don\'t lie in subtree of src means this hight is safe and be counted\n        if(g[mid][0].first < in[src] || g[mid][0].second > out[src]) return 1;\n\n        // check if last vertex don\'t lies in subtree of src\n\t\t// Checking first and last is sufficient becase other middle vartices are in range of timings\n        if(g[mid].back().first < in[src] || g[mid].back().second > out[src]) return 1;\n\n\n        return 0;\n    }\n\n    vector<int> treeQueries(TreeNode* root, vector<int>& queries) {\n\n        for(int i=0;i;i++)\n        {\n            if(g[i].size() == 0)break;\n            g[i].clear();\n        }\n\n        // resetting \n        timer = 0;\n        mx = 0;\n        dfs(root,0);\n        \n        \n        vector<int> ans;\n\n        for(int q:queries)\n        {\n            int lo = 0;\n            int hi = mx;\n            int h = 1;\n\n            while(lo <= hi)\n            {\n                int mid = (lo + hi) / 2;\n\n                if(check(mid,q))\n                {\n                    h = mid;\n                    lo = mid + 1;\n                }\n                else\n                {\n                    hi = mid - 1;\n                }\n            }\n\n            ans.push_back(h);\n        }\n\n        return ans;\n    }\n};\n```\n\n\n\n\n\n\n\n\n\n\n\n\n
['C']