EULER TOUR
\tclass Solution {\n\tpublic:\n\t\tvoid dfs(int src, vector> &adj, vector &euler){\n\t\t\teuler.push_back(src);\n\t\t\tfor(auto &it : adj[src]){\n\t\t\t\tdfs(it
\tclass Solution {\n\tpublic:\n\t\tvoid dfs(int src, vector<vector<int>> &adj, vector<int> &euler){\n\t\t\teuler.push_back(src);\n\t\t\tfor(auto &it : adj[src]){\n\t\t\t\tdfs(it, adj, euler);\n\t\t\t}\n\t\t\teuler.push_back(src);\n\t\t\treturn;\n\t\t}\n\t\tvector<int> smallestMissingValueSubtree(vector<int>& parents, vector<int>& nums) {\n\t\t\tint n = nums.size();\n\t\t\tvector<vector<int>> adj(n);\n\t\t\tvector<int> ans(n, 1);\n\t\t\tint node= -1;\n\t\t\tfor(int i=1; i<n; i++){\n\t\t\t\tadj[parents[i]].push_back(i);\n\t\t\t}\n\t\t\tfor(int i=0; i<n; i++){\n\t\t\t\tif(nums[i] == 1) {\n\t\t\t\t\tnode = i;\n\t\t\t\t\tbreak;\n\t\t\t\t}\n\t\t\t}\n\t\t\tif(node == -1){\n\t\t\t\treturn ans;\n\t\t\t}\n\t\t\tvector<int> euler;\n\t\t\tdfs(0, adj, euler);\n\t\t\tint l = -1, r = -1;\n\t\t\tfor(int i=0; i<euler.size(); i++){\n\t\t\t\tif(euler[i] == node){\n\t\t\t\t\tif(l == -1) l = i;\n\t\t\t\t\telse r = i;\n\t\t\t\t}\n\t\t\t}\n\t\t\tvector<bool> value(1e5 + 5, false);\n\t\t\tint currans = 1;\n\t\t\tfor(int i=l; i<=r; i++){\n\t\t\t\tvalue[nums[euler[i]]] = true;\n\t\t\t\tif(currans == nums[euler[i]]){\n\t\t\t\t\twhile(value[currans] == true) currans++;\n\t\t\t\t}\n\t\t\t}\n\t\t\tans[node] = currans;\n\t\t\twhile(parents[node] != -1){\n\t\t\t\tnode = parents[node];\n\t\t\t\twhile(euler[l] != node) {\n\t\t\t\t\tl--;\n\t\t\t\t\tvalue[nums[euler[l]]] = true;\n\t\t\t\t\tif(currans == nums[euler[l]]){\n\t\t\t\t\t\twhile(value[currans] == true) currans++;\n\t\t\t\t\t}\n\t\t\t\t}\n\t\t\t\twhile(euler[r] != node) {\n\t\t\t\t\tr++;\n\t\t\t\t\tvalue[nums[euler[r]]] = true;\n\t\t\t\t\tif(currans == nums[euler[r]]){\n\t\t\t\t\t\twhile(value[currans] == true) currans++;\n\t\t\t\t\t}\n\t\t\t\t}\n\t\t\t\tans[node] = currans;\n\t\t\t}\n\t\t\treturn ans;\n\n\n\n\t\t}\n\t};
['Two Pointers', 'Depth-First Search']