C++| Euler tour
Prerequisite: Eular Tour\n\nFor every node, store the following things:\n1. Time of discovery (TOD)\n1. Height of node\n1. No. of nodes/children in its subtree\
**Prerequisite: Eular Tour**\n\nFor every node, store the following things:\n1. Time of discovery (**TOD**)\n1. Height of node\n1. No. of nodes/children in its subtree\n\n* Once the above parameters are stored, we can find the range of TOD of every node present in any subtree of some node. Ex: suppose that for a node `x`, TOD is `in` and no. of children are `y`, then all the node with TOD between **in** to **in+y** lies in the subtree of node `x`. To find the height of tree, we have to avoid these nodes for any `queries[i] = x`.\n* To do the above operation and find height in O(1), We need to maintain prefix and suffix array. For each TOD, store its height and compute max height of TOD from `0 to i` in preffix and store max of height of TOD from `i to n` in suffix. Rest will be clear from code.\n```\nclass Solution {\npublic:\n    int dfs(TreeNode* root,map<int,vector<int>> &mp,int h,int &n){\n        if(!root) return 0;\n        int no = n++;\n        int sum = dfs(root->left,mp,h+1,n)+dfs(root->right,mp,h+1,n);\n        mp[root->val] = {no,h,sum}; // {time of discovery, height of node, no. of children}\n        return sum+1;\n    }\n    vector<int> treeQueries(TreeNode* root, vector<int>& q) {\n        map<int,vector<int>> mp;\n        int x = 0;\n        dfs(root,mp,0,x);\n        int n = mp.size();\n        vector<int> left(n+1,0),right(n+1,0);\n        \n        for(auto it = mp.begin(); it!=mp.end();++it){\n            left[it->second[0]] = it->second[1];\n            right[it->second[0]] = it->second[1];\n        }\n        \n        for(int i = 1; i<n;++i) left[i] = max(left[i-1],left[i]);\n        for(int i = n-1;i>=0;--i) right[i] = max(right[i],right[i+1]);\n        \n        vector<int> re(q.size(),0);\n        for(int i = 0; i<q.size();++i){\n            int l = mp[q[i]][0]-1, h = mp[q[i]][0]+mp[q[i]][2]+1;\n            if(l>=0) re[i] = left[l];\n            if(h<n) re[i] = max(re[i],right[h]);\n        }\n        return re;\n    }\n};\n```\n**Upvote if it helps **
['Depth-First Search', 'C']