DFS C++ SOLUTION
Intuition\nStart from the node which has value 1.\nGo to its subtree before going up continue for other nodes too.\n\n\n# Complexity\n- Time complexity:\nO(N)\n
# Intuition\nStart from the node which has value 1.\nGo to its subtree before going up continue for other nodes too.\n\n\n# Complexity\n- Time complexity:\n$$O(N)$$\n\n- Space complexity:\n$$O(N)$$\n\n# Code\n```\nclass Solution {\npublic:\n    int height[100005];\n    set<int>s;\n    void dfs(int x, int par, vector<int>v[],int h)\n    {\n        height[x]=h;\n        for(int i=0; i<v[x].size(); i++)\n        {\n            int child=v[x][i];\n            if(child!=par)\n            {\n                dfs(child,x,v,h+1);\n            }\n        }\n    }\n    void dfs1(int x, vector<int>v[], vector<int>&ans, int k, vector<int>&nums)\n    {\n        s.erase(nums[x]);\n        for(int i=0; i<v[x].size(); i++)\n        {\n            int c=v[x][i];\n            if(height[c]>height[x])\n            {\n                dfs1(c,v,ans,k,nums);\n            }\n        }\n    }\n\n    void dfs2(int x, vector<int>v[], vector<int>&ans, int k, int par, vector<int>&nums)\n    {\n        if(s.find(nums[x])!=s.end()) s.erase(nums[x]);\n        int calc=-1;\n        for(int i=0; i<v[x].size(); i++)\n        {\n            int c=v[x][i];\n            if(c==par) continue;\n            if(k==0)\n            {\n                if(height[c]<height[x])\n                {\n                    calc=c;\n                }\n                else\n                {\n                    dfs2(c,v,ans,1,x,nums);\n                }\n            }\n            else\n            {\n                dfs2(c,v,ans,1,x,nums);\n            }\n        }\n        if(k==1) ans[x]=1;\n        else\n        {\n            auto it=s.begin();\n            ans[x]=(*it);\n        }\n        if(k==0 && calc!=-1)\n        {\n            dfs2(calc,v,ans,k,x,nums);\n        }\n    }\n\n    vector<int> smallestMissingValueSubtree(vector<int>& parents, vector<int>& nums) {\n        \n        s.clear();\n        int n=parents.size(),root=0;\n        vector<int>ans(n,-1);\n        vector<int>v[n+1];\n        for(int i=1; i<n; i++)\n        {\n            v[parents[i]].push_back(i);\n            v[i].push_back(parents[i]);\n            if(nums[i]==1) root=i;\n        }\n        dfs(0,-1,v,1);\n        for(int i=1; i<=n+1; i++) s.insert(i);\n        dfs1(root,v,ans,root,nums);\n        dfs2(root,v,ans,0,-1,nums);\n        return ans;\n    }\n};\n```
['C++']