Code Nation OA 2021 Question | C++, easy to understand, clean | O(N)
This was one of the three questions in Code Nation OA test 2021. \n\nFirstly, we only need to find the missing number for the nodes which are ancestors of the n
This was one of the three questions in Code Nation OA test 2021. \n\nFirstly, we only need to find the missing number for the nodes which are ancestors of the node having value of "1". Once we figure this out, it is straight forward. Suppose we are at node whose value is 1, for this node we would like to find out what all values are present in its subtree. This can be done using a post order traversal, and marking all the values that were visited. Here, it is done using the set visited. Since all the values are unique, we can use the same set for out traversal visit also. \n\nAfter finding all the values that have been visited in the subtree of the node with value one, we need to move to its parent, and repeat the same process. After each of the traversal, we need to check what is the next missing value.\n\nThe code is pretty much self explainatory!\n\n\n```\nclass Solution {\npublic:\n    unordered_set<int> visited; \n    vector<int> nums ;\n    vector<vector<int>> adj;\n    \n    void dfs(int node){\n        for(auto child:adj[node]){\n            if(!visited.count(nums[child])){\n                visited.insert(nums[child]);\n                dfs(child); \n            }\n        }\n    }\n    \n    vector<int> smallestMissingValueSubtree(vector<int>& parents, vector<int>& nums) {\n        int n = parents.size(), missing = 1; \n        adj.resize(n);\n        vector<int> res;\n        this->nums = nums; \n        res.resize(n,1); \n        \n        for(int i=1; i<n; i++) adj[parents[i]].push_back(i); \n    \n        int node = -1; \n        for(int i=0; i<n; i++){\n            if(nums[i] == 1) {\n                node = i; \n                break ; \n            }\n        }\n        if(node == -1) return res; \n        while(node != -1) {\n            visited.insert(nums[node]); \n            dfs(node); \n            while(visited.count(missing)) missing++; \n            res[node] = missing;     \n            node = parents[node]; \n        }\n        return res; \n    }\n};\n```
['C']