Visualization with code | C++
Visualization\nLet\'s say we have a tree like this where value = 1 is present somewhere in the middle. Let\'s call this node as u\n\nWe can eliminate the yellow
**Visualization**\nLet\'s say we have a tree like this where value = 1 is present somewhere in the middle. Let\'s call this node as ```u```\n![image](https://assets.leetcode.com/users/images/eef5dd40-6886-4d36-8f20-a1cb2aea82ce_1631438610.3941283.png)\nWe can eliminate the yellow region as shown below\n![image](https://assets.leetcode.com/users/images/2a3af227-aeb8-4b7e-81c0-e8db3dcf6e2e_1631438745.774424.png)\nNow we are left with only descendants of the node where value = 1 is present as shown below\n![image](https://assets.leetcode.com/users/images/638bdd8e-efe9-4f49-b4fd-7782d353c0f9_1631438861.9651783.png)\n\n1. Now start with ```number``` = 2 initially\n2. For ( ```v``` = ```u```  to ```root```) we do steps 3 to 5\n3. Check the subtree rooted at ```v``` to see if  ```number``` is present in the subtree. We want to do it in O(1) lookup. Lets say some function ```cicada``` can help us do it.\n3. If number is not present in subtree rooted at ```v``` --> ```ans[v] = number , v = parent[v]``` (move to the ancestor in upward direction. Note: For the ancestor all numbers till ```number-1``` are already present in the subtree rooted at ancestor )\n4. else ```number++``` (search for next smaller number)\n\n**How will cicada work?**\n1. In the begin itself (as a preprocessing step), perform preorder traversal and assign labels as we go along to the nodes starting from node 0 (in the code labelling starts with 0 but in below visualization labelling starts at 1)\n2. Since the values are unique, maintain 2 maps \n\t* ```valToLabelMap``` -> given a value of the node it gives us the label in the preorder labelled node\n\t* ```lastChildLabelMap``` -> given the value of the node it gives us the label of the last child node sub rooted under node with value.\n3. Now given any ```number``` and a node ```v``` we can first obtain its the label range (left ans right labels) which ```v``` commands and the label of ```number```.\n4. If ```if(left <= labelOfNum && labelOfNum <= right)``` we know the ```number``` is present in the subtree rooted at ```v``` else not\n5. Refer below for visualization\n![image](https://assets.leetcode.com/users/images/92bce779-2181-42aa-9847-e32a94ab3ff2_1631440341.6691904.png)\n\n\n\n**Code**\n```\nclass Solution {\npublic:\n    vector<int> smallestMissingValueSubtree(vector<int>& parent, vector<int>& a) {\n        int n = a.size();\n        vector<int> ans(n, 1);\n        vector<vector<int>> graph(n);\n        vector<int> valToPosMap(100002, -1);\n        for(int i = 0 ; i < n; i++){\n            if(parent[i] != -1){\n                graph[parent[i]].push_back(i);\n            }\n            valToPosMap[a[i]] = i;\n        }\n        vector<int> valToLabelMap(100002, -1), lastChildLabelMap(100002, -1);\n        int label = 0;\n        preorderLabel(valToLabelMap, a, graph, 0, label, lastChildLabelMap);\n        \n        if(valToLabelMap[1] == -1) return ans;\n        \n        int child = valToPosMap[1];\n        int num = 2;\n        while(child != -1){\n            int value = a[child];\n            int left = valToLabelMap[value];\n            int right = lastChildLabelMap[value];\n            int labelOfNum = valToLabelMap[num];\n            if(left <= labelOfNum && labelOfNum <= right) num++;\n            else{\n                ans[child] = num;\n                child = parent[child];\n            }\n        }\n        return ans;\n    }\n    \n    void preorderLabel(vector<int> &valToLabelMap, vector<int> &a, vector<vector<int>> &graph, int u, int &label, vector<int> &lastChildLabelMap){\n        int value = a[u];\n        valToLabelMap[value] = label++;\n        int labelHere = label-1;\n        for(auto &v : graph[u]){\n            preorderLabel(valToLabelMap, a, graph, v, label, lastChildLabelMap);\n        }\n        lastChildLabelMap[value] = label-1;\n    }\n};\n```
['C']