C++ | DFS
Subtrees which don\'t include node with genetic value 1, have answer = 1.\nSo we need to find the answer for subrees containing with node having genetic value =
Subtrees which don\'t include node with genetic value 1, have answer = 1.\nSo we need to find the answer for subrees containing with node having genetic value = 1.\n\nWe can get the node with genetic value = 1, by traversing in the nums array. From that we have to go to the parent node = 0, then apply DFS at each node in the path. In this DFS, we are putting finded values in map. We will have pointer which defines, the smallest genetic value. \n\n# Code\n```\nclass Solution {\npublic:\n\n    vector<int> arr[100001];\n    bool mp[100001];\n\n\n    //excludeChild is used to exclude the node for which dfs is already done.\n    void dfs(int cur, int excludeChild, vector<int>&nums){\n        for(int i=0;i<arr[cur].size();i++){\n            if(arr[cur][i]!=excludeChild)\n                dfs(arr[cur][i],-1,nums);\n        }\n        mp[nums[cur]] = true;\n    }\n\n    vector<int> smallestMissingValueSubtree(vector<int>& parents, vector<int>& nums) {\n        int n = parents.size();\n        memset(mp,false, sizeof(mp));\n        mp[0] = true;\n        vector<int>ans(n,-1);\n    \n        //creating tree with adjacency list\n        for(int i=1;i<n;i++)\n            arr[parents[i]].push_back(i);\n\n        //finding the node with genetic value 1\n        int nodeWithOne = -1;\n        for(int i=0;i<n;i++){\n            if(nums[i]==1){\n                nodeWithOne = i;\n                break;\n            }\n        }\n\n        //running dfs at each node which comes in path of node with value 1\n        int prev = -1;\n        int minEnergy = 0;\n        if(nodeWithOne!= -1){\n            \n            int cur = nodeWithOne;\n            while(cur>=0){\n                if(cur==nodeWithOne)\n                    dfs(cur,-1,nums);\n                else\n                    dfs(cur,prev,nums);\n\n                while(minEnergy<=100000 && mp[minEnergy])\n                    minEnergy++;\n                ans[cur] = minEnergy;\n\n                prev = cur;\n                cur = parents[cur];\n            }\n        }\n        for(int i=0;i<n;i++)\n            if(ans[i]==-1)\n                ans[i] = 1;\n\n        return ans;\n    }\n};\n```
['Depth-First Search', 'C++']