Nice idea of controlling the order of exploration (BFS/DFS): 43 ms | Beats 96%
IntuitionConsider this - what if there was no node with gene value 1, then answer would be 1 for all nodes
Now focus on node x with value 1since gene values are
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
Consider this - what if there was no node with gene value 1, then answer would be 1 for all nodes
Now focus on node `x` with value `1`
```
          0
        / | \
       a  b  c
         /
        .
        .
        y
       /  \
     x(1)  d
      |
      △

```
since gene values are distinct, every node in the subtree of `x` will also have answer `1`, similarly for every node that is not `x` or ancestor of `x` (e.g. `a, c, d`), will also have answer `1` since they dont have `1`.
Now how do we find the answer for `x`? 

We can explore its subtree first, mark all gene values we saw, then check every value from 2,3,4.. till we find a value that was not seen.

Then same thing with its ancestor `y`. Explore rest of the children of y, and update its min missing gene.

# Complexity
- Time complexity: O(n)
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity: O(n)
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```java []
class Solution {
  BitSet seen = new BitSet(); // to keep track of seen gene values
  List<List<Integer>> graph = new ArrayList<>();
  int[] nums;
  
  public int[] smallestMissingValueSubtree(int[] parents, int[] nums) {
    int n = nums.length;
    int[] ans = new int[n];
    Arrays.fill(ans, 1);
    
    // find node with gene value 1
    int nodeWithGene1 = -1;
    for (int i = 0; i<n; ++i) {
      if (nums[i] == 1) {
        nodeWithGene1 = i;
        break;
      }
    }
    if (nodeWithGene1 == -1) return ans;

    // build graph
    this.nums = nums;
    for (int i = 0; i<n; ++i) {
      graph.add(new ArrayList<>());
    }
    for (int i = 1; i<n; ++i) {
      graph.get(parents[i]).add(i);
    }

    // invoke dfs first from node with gene value 1, then its parent,
    // and so on till root
    int curNode = nodeWithGene1;
    int prevOnPath = -1;
    int minMissingGene = 2;
    while(curNode != -1) {
      seen.set(nums[curNode]);
      for (int child: graph.get(curNode)) {
        if (child == prevOnPath) continue;
        dfs(child);
      }
      while(seen.get(minMissingGene)) {
        ++minMissingGene;
      }
      ans[curNode] = minMissingGene;
      prevOnPath = curNode;
      curNode = parents[curNode];
    }
    return ans;
  }

  void dfs(int root) {
    seen.set(nums[root]);
    for (int child: graph.get(root)) {
      dfs(child);
    }
  }
}
```
['Java']