Tree Traverse
Because 1 is the minimal value, the idea is to mark all the children of node with val = 1, says Node1, to 1.\nAll nodes are not on the path from root to Node1 s
Because 1 is the minimal value, the idea is to mark all the children of node with val = 1, says Node1, to 1.\nAll nodes are not on the path from root to Node1 should also be 1.\nOn the path from Node1 to root, we can gradually increase the value by checking all the subtrees.\n\nAs stated above, all nodes except those on the path from Node1 to root would has 1 as the smallest generic value. We can first set all values to be 1 and only update those on the path by collecting all values in the subtree.\n```java\nclass Solution {\n    public int[] smallestMissingValueSubtree(int[] parents, int[] nums) {\n        int[] res = new int[nums.length];\n        \n        List<Integer>[] children = new List[nums.length];\n        int node1Idx = -1;\n        for (int i = 1; i < parents.length; ++i) {\n            if (children[parents[i]] == null) {\n                children[parents[i]] = new ArrayList<>();\n            }\n            children[parents[i]].add(i);\n            if (nums[i] == 1) {\n                node1Idx = i;\n            }\n        }\n        \n        if (nums[0] == 1) {\n            node1Idx = 0;\n        }\n        Arrays.fill(res, 1);\n        if (node1Idx < 0) {\n            return res;\n        }\n        \n        Set<Integer> visited = new HashSet<>();\n        int min = 1;\n        while (node1Idx >= 0) {\n            dfs(children, node1Idx, nums, res, visited, min);\n            while (visited.contains(min)) {\n                min++;\n            }\n            res[node1Idx] = min;\n            node1Idx = parents[node1Idx];\n        }\n        \n        return res;\n        \n        \n    }\n    \n    private void dfs(List<Integer>[] children, int id, int[] nums, int[] res, Set<Integer> visited, int min) {\n        if (!visited.add(nums[id])) {\n            return;\n        }\n        if (children[id] != null) {\n            for (int childId : children[id]) {\n                dfs(children, childId, nums, res, visited, min);\n            }\n        }\n    }\n}\n```\nAs the above solution would travel the entire tree to collect values. We can combine the assign 1 and collecting values in one recursive call.\n```java\nclass Solution {\n    /* \n    */\n    public int[] smallestMissingValueSubtree(int[] parents, int[] nums) {\n        int[] res = new int[nums.length];\n        \n        // put all the children nodes in an array to travel down.\n        List<Integer>[] children = new List[nums.length];\n        // find Idx of Node1 at the same time\n        int node1Idx = -1;\n        // we skip the root node as its parent is -1.\n        for (int i = 1; i < parents.length; ++i) {\n            if (children[parents[i]] == null) {\n                children[parents[i]] = new ArrayList<>();\n            }\n            children[parents[i]].add(i);\n            if (nums[i] == 1) {\n                node1Idx = i;\n            }\n        }\n        // Don\'t forget the root node can be 1 as well\n        if (nums[0] == 1) {\n            node1Idx = 0;\n        }\n        // If no Node1.all the smallest genetic value should be 1\n        if (node1Idx < 0) {\n            Arrays.fill(res, 1);\n            return res;\n        }\n        // set to record node value\n        Set<Integer> visited = new HashSet<>();\n        \n        recur(children, node1Idx, parents, nums, res, visited, 1, -1);\n        return res;\n        \n        \n    }\n    \n    private void recur(List<Integer>[] children, int id, int[] parents, int[] nums, int[] res, Set<Integer> visited, int min, int stop) {\n        // becaues it is needed traverse up in later stage. A stop mark should make sure it only travel within the subtree\n        if (id == stop) {\n            return;\n        }\n        // for all the branches, they should be step to 1.\n        if (children[id] != null) {\n            for (int i : children[id]) {\n                if (res[i] > 0) {\n                    continue;\n                }\n\t\t\t\t// if it is not on the path from Node1 to root, it should be set to 1.\n                res[i] = 1;\n                visited.add(nums[i]);\n\t\t\t\t// same here. the smallest generic value should be 1\n                recur(children, i, parents, nums, res, visited, 1, id);\n            }\n        }\n        // check if the min is still the small value. if the current value is min or min is in the subtree, it would be increased until a unseen min is met.\n        while (nums[id] == min || visited.contains(min)) {\n            min++;\n        }\n        // 1 would not be added in the set as nodes of sibling branches of Node 1 would be set to 1. \n        if (nums[id] > 1) {\n            visited.add(nums[id]);\n        }\n        res[id] = min;\n        recur(children, parents[id], parents, nums, res, visited, min, stop);\n    }\n}\n```
['Depth-First Search', 'Java']