C++ | Optimised DFS | O(N)
Visited checks if any node(by value) is visited before. \ncurNode is the node on which dfs will be applied and curMinNo will go from 1 linearly to max value.\ng
Visited checks if any node(by value) is visited before. \ncurNode is the node on which dfs will be applied and curMinNo will go from 1 linearly to max value.\nget index of 1(by value) and start dfs, one optimization in dfs is if (!visited()).\nTime Complexity-O(N) [for simple dfs its O(N) and curMinNo is linearly increasing in itself]\nSpace Complexity-O(N)\n```\nclass Solution {\npublic:\n    void dfs(int cur,vector<int> &visited,vector<int>& nums,map<int,vector<int>> &tree){\n        if (!visited[nums[cur]]){\n            visited[nums[cur]]=true;\n            for (auto i:tree[cur]) dfs(i,visited,nums,tree);\n        }\n    }\n    vector<int> smallestMissingValueSubtree(vector<int>& parents, vector<int>& nums) {\n        ios_base::sync_with_stdio(false);cin.tie(NULL);\n        int n=nums.size();\n        vector<int> ans(n,1);\n        if (count(nums.begin(),nums.end(),1)==0) return ans;\n        map<int,vector<int>> tree;\n        for (int i=0;i<n;i++){\n            tree[parents[i]].push_back(i);\n        }\n        vector<int> visited(*max_element(nums.begin(),nums.end())+2,false);\n        int curNode=find(nums.begin(),nums.end(),1)-nums.begin();\n        int curMissNo=1;\n        while (curNode!=-1){\n            dfs(curNode,visited,nums,tree);\n            while (visited[curMissNo]) curMissNo++;\n            ans[curNode]=curMissNo;\n            curNode=parents[curNode];\n        }\n        return ans;\n    }\n};\n```
['Depth-First Search', 'C']