C++ DFS Solution O(N)
Runtime: 364 ms, faster than 88.19% of C++ online submissions for Smallest Missing Genetic Value in Each Subtree.\nMemory Usage: 139 MB, less than 88.89% of C++
Runtime: 364 ms, faster than 88.19% of C++ online submissions for Smallest Missing Genetic Value in Each Subtree.\nMemory Usage: 139 MB, less than 88.89% of C++ online submissions for Smallest Missing Genetic Value in Each Subtree.\n\n\n```\nOnly the node of the path which lead to genetic value 1 will have smallest missing value greater than 1.\nOther nodes will have smallest missing values 1.\n\nSo we find the node which has genetic value 1 and then move upward to the parent node until reach root.\nEach step we mark the genetic value of the subtree nodes using DFS.\nFirst unmarked value is the smallest missing value.\n```\n\n```\nclass Solution {\npublic:\n    \n    // recursively mark the genetic value of the subtree nodes\n    void dfs(int index, vector<vector<int>>&tree, vector<int>&nums, vector<bool>&visited, vector<bool>&vals)\n    {\n        visited[index] = true;\n        if(nums[index]<vals.size())\n            vals[nums[index]]=true;\n        \n        for(int i=0;i<tree[index].size();i++)\n            if(!visited[tree[index][i]])\n                dfs(tree[index][i],tree,nums,visited,vals);        \n    }\n    \n    vector<int> smallestMissingValueSubtree(vector<int>& parents, vector<int>& nums) {\n        \n        // create tree from the given parent list\n        int n = parents.size();\n        vector<vector<int>>tree(n);\n        \n        for(int i=1;i<n;i++)\n            tree[parents[i]].push_back(i);\n        \n\n        // all nodes result is 1 initially\n        vector<int>ans(n,1);        \n        \n        // find the index of node which has genetic value 1\n        int oneIndex = -1;\n        for(int i=0;i<n;i++)\n        {\n            if(nums[i]==1)\n            {\n                oneIndex = i;\n                break;\n            }            \n        }\n        \n        // if there is no node with genetic value 1 then all nodes result is 1\n        if(oneIndex==-1)return ans;\n        \n        // node visiting track for DFS\n        vector<bool>visited(n,false); \n        \n        // mark taken genetic value\n        vector<bool>vals(n+2,false);\n        \n        // first missing value is 1\n        int miss = 1;\n        \n        // starting from node with genetic value 1 move upward to the root        \n        while(oneIndex!=-1)\n        {\n            // each step run DFS to mark the genetic value of all its descendant nodes\n            dfs(oneIndex,tree,nums,visited,vals);\n            \n            // get first unmarked value which is the missing value for current node\n            while(vals[miss])miss++;\n            \n            ans[oneIndex] = miss;\n            \n            // move upward to parent node\n            oneIndex = parents[oneIndex];\n        }\n        \n        return ans;\n    }\n};\n```
['Depth-First Search', 'Graph', 'C']