java O(N)
Not a novel idea, adapted from other posts. Basically traverse up from node with value 1 to root, only traversing down to count other subtrees, but we do not wr
Not a novel idea, adapted from other posts. Basically traverse up from node with value 1 to root, only traversing down to count other subtrees, but we do not write to result for the downwards traversals, since they do not lie on the path from node with value 1 to root.\n\n```\nclass Solution {\n    public int[] smallestMissingValueSubtree(int[] parents, int[] nums) {\n        int n = nums.length;\n        Set<Integer> set = new HashSet<>();\n        Map<Integer, List<Integer>> graph = new HashMap<>();\n        boolean[] visited = new boolean[n];\n        int start = -1;\n        for (int i=0; i<parents.length; i++) {\n            graph.putIfAbsent(parents[i], new ArrayList<>());\n            graph.get(parents[i]).add(i);\n            if (nums[i] == 1) {\n                start = i;\n            }\n        }\n        int[] res = new int[n];\n        Arrays.fill(res, 1);\n        int[] cnt = new int[]{1};\n\n        dfs(graph, nums, parents, start, res, cnt, set, visited, true);\n        \n        return res;\n    }\n    \n    private void dfs(Map<Integer, List<Integer>> graph , int[] nums, int[] parents, int i, int[] res, int[] cnt, Set<Integer> set, boolean[] visited, boolean write) {\n        if (i == -1 || visited[i]) {\n            return;\n        }\n        set.add(nums[i]);\n        visited[i] = true;\n        for (int nxt: graph.getOrDefault(i, new ArrayList<>())) {\n            dfs(graph, nums, parents, nxt, res, cnt, set, visited, false);\n        }\n        \n        while (set.contains(cnt[0])) {\n            ++cnt[0];\n        }\n        if (write) {\n            res[i] = cnt[0];\n        }\n        \n        dfs(graph, nums, parents, parents[i], res, cnt, set, visited, true);\n    }\n}\n```
[]