C++ O(n) solution using BFS, no recursion. < 40 lines
\nclass Solution {\npublic:        \n    vector<int> smallestMissingValueSubtree(vector<int>& parents, vector<int>& nums) {\n        int n = parents.size();\n  
```\nclass Solution {\npublic:        \n    vector<int> smallestMissingValueSubtree(vector<int>& parents, vector<int>& nums) {\n        int n = parents.size();\n        vector<vector<int>> Tree(n);\n        for(int i=1; i<n; i++) Tree[parents[i]].push_back(i);    //  build the tree\n        vector<int> ans(n,1);\n        int k = -1;\n        for(int i=0; i<n; i++){\n            if(nums[i]==1){\n                k = i;\n                break;\n            }\n        }\n        if(k==-1) return ans;  // check whether if 1 exist in vector<int>nums\n        vector<bool> visited_gene_set(100002,false);  // used to find current minimum unvisited gene\n        int do_not_visit = -1;   // index we no longer need to visit because it has been visited in the previous while loop\n        int cur_min = 1, front;  \n        while(k!=-1){  // while there is still node unvisited in path (gene:1 -> root)\n            queue<int> q;  \n            q.push(k);  // start bfs from that node\n            while(!q.empty()){\n                front = q.front();\n                q.pop();\n                visited_gene_set[nums[front]] = true;\n                for(auto& child:Tree[front])\n                    if(child!=do_not_visit) q.push(child);  // ignore previous node upon which we have used bfs\n            }\n            while(visited_gene_set[cur_min]) cur_min++;  // search current minimum, at most O(n)\n            ans[k] = cur_min;\n            do_not_visit = k;\n            k = parents[k];   // visit next node in path (gene:1 -> root)\n        }\n        return ans;\n    }\n};\n```
['Breadth-First Search', 'C']