# Smallest Missing Genetic Value in Each Subtree
**Difficulty:** HARD
[External](https://leetcode.com/problems/smallest-missing-genetic-value-in-each-subtree)
Canonical: https://scaleengineer.com/dsa/problems/smallest-missing-genetic-value-in-each-subtree
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Union Find](https://scaleengineer.com/algorithms/union-find)
**Data structures:** Tree
---
## Problem
There is a **family tree** rooted at `0` consisting of `n` nodes numbered `0` to `n - 1`. You are given a **0-indexed** integer array `parents`, where `parents[i]` is the parent for node `i`. Since node `0` is the **root**, `parents[0] == -1`.

There are `105` genetic values, each represented by an integer in the **inclusive** range `[1, 105]`. You are given a **0-indexed** integer array `nums`, where `nums[i]` is a **distinct** genetic value for node `i`.

Return _an array_ `ans` _of length_ `n` _where_ `ans[i]` _is_ _the **smallest** genetic value that is **missing** from the subtree rooted at node_ `i`.

The **subtree** rooted at a node `x` contains node `x` and all of its **descendant** nodes.

**Example 1:**

![](https://assets.glich.co/dsa/smallest-missing-genetic-value-in-each-subtree/image0.png) 

**Input:** parents = [-1,0,0,2], nums = [1,2,3,4]
**Output:** [5,1,1,1]
**Explanation:** The answer for each subtree is calculated as follows:
- 0: The subtree contains nodes [0,1,2,3] with values [1,2,3,4]. 5 is the smallest missing value.
- 1: The subtree contains only node 1 with value 2. 1 is the smallest missing value.
- 2: The subtree contains nodes [2,3] with values [3,4]. 1 is the smallest missing value.
- 3: The subtree contains only node 3 with value 4. 1 is the smallest missing value.

**Example 2:**

![](https://assets.glich.co/dsa/smallest-missing-genetic-value-in-each-subtree/image1.png) 

**Input:** parents = [-1,0,1,0,3,3], nums = [5,4,6,2,1,3]
**Output:** [7,1,1,4,2,1]
**Explanation:** The answer for each subtree is calculated as follows:
- 0: The subtree contains nodes [0,1,2,3,4,5] with values [5,4,6,2,1,3]. 7 is the smallest missing value.
- 1: The subtree contains nodes [1,2] with values [4,6]. 1 is the smallest missing value.
- 2: The subtree contains only node 2 with value 6. 1 is the smallest missing value.
- 3: The subtree contains nodes [3,4,5] with values [2,1,3]. 4 is the smallest missing value.
- 4: The subtree contains only node 4 with value 1. 2 is the smallest missing value.
- 5: The subtree contains only node 5 with value 3. 1 is the smallest missing value.

**Example 3:**

**Input:** parents = [-1,2,3,0,2,4,1], nums = [2,3,4,5,6,7,8]
**Output:** [1,1,1,1,1,1,1]
**Explanation:** The value 1 is missing from all the subtrees.

**Constraints:**

* `n == parents.length == nums.length`
* `2 <= n <= 105`
* `0 <= parents[i] <= n - 1` for `i != 0`
* `parents[0] == -1`
* `parents` represents a valid tree.
* `1 <= nums[i] <= 105`
* Each `nums[i]` is distinct.

# Approaches
## Brute-Force Traversal for Each Subtree
A straightforward approach is to iterate through each node, and for each node, determine its subtree. Then, we collect all the genetic values within that subtree and find the smallest positive integer not present in the collection. This method is easy to conceptualize but computationally expensive.
**Time:** O(N^2). We iterate through N nodes. For each node `i`, we traverse its subtree. The size of a subtree can be up to N. The sum of all subtree sizes can be O(N^2) in the worst case (a path or skewed tree). For each subtree, collecting values and finding the missing one takes time proportional to the subtree size. Thus, the total time complexity is O(N^2). · **Space:** O(N). The adjacency list requires O(N) space. During the calculation for each node, the `HashSet` can grow to store up to N values in the worst case (for the root's subtree), thus requiring O(N) auxiliary space. The recursion stack for DFS can also go up to O(N) in depth for a skewed tree.
**Pros:** - It is simple to understand and implement.; - It correctly solves the problem for small inputs.
**Cons:** - The time complexity is O(N^2) in the worst-case scenario (e.g., a skewed tree), which is too slow for the given constraints and will result in a 'Time Limit Exceeded' error on most platforms.
### Explanation
This approach tackles the problem directly by processing each node one by one. For every node `i` in the tree, we need to find the smallest missing genetic value in its subtree.

First, we convert the `parents` array into a more convenient graph representation, like an adjacency list, where `adj[u]` contains all children of node `u`. This allows for easy traversal of subtrees.

Then, for each node `i` from `0` to `n-1`, we perform a traversal (e.g., DFS) starting from `i`. This traversal visits `i` and all of its descendants. During the traversal, we use a `HashSet` to collect the distinct genetic values (`nums`) of all the nodes in the current subtree. The `HashSet` provides fast O(1) average time complexity for insertions and lookups.

Once the set of genetic values for the subtree of `i` is complete, we search for the smallest missing positive integer. We start checking from `1` and increment upwards, using the `contains` method of the hash set to see if the number is present. The first integer we find that is not in the set is the answer for the subtree rooted at `i`.

We repeat this entire process for all `n` nodes to fill the final answer array.

```java
import java.util.*;

class Solution {
    public int[] smallestMissingValueSubtree(int[] parents, int[] nums) {
        int n = parents.length;
        List<List<Integer>> children = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            children.add(new ArrayList<>());
        }
        for (int i = 1; i < n; i++) {
            children.get(parents[i]).add(i);
        }

        int[] ans = new int[n];
        for (int i = 0; i < n; i++) {
            Set<Integer> subtreeValues = new HashSet<>();
            collectSubtreeValues(i, children, nums, subtreeValues);
            
            int missing = 1;
            while (subtreeValues.contains(missing)) {
                missing++;
            }
            ans[i] = missing;
        }
        return ans;
    }

    private void collectSubtreeValues(int u, List<List<Integer>> children, int[] nums, Set<Integer> values) {
        values.add(nums[u]);
        for (int v : children.get(u)) {
            collectSubtreeValues(v, children, nums, values);
        }
    }
}
```
### Algorithm
- 1. Construct an adjacency list for the tree from the `parents` array to represent the child-parent relationships.
- 2. Initialize an answer array `ans` of size `n`.
- 3. Iterate through each node `i` from `0` to `n-1`.
- 4. For each node `i`:
    - a. Create an empty `HashSet` to store the genetic values of the nodes in the subtree of `i`.
    - b. Perform a Depth First Search (DFS) or Breadth First Search (BFS) starting from node `i` to traverse its entire subtree.
    - c. For each node `j` visited in the traversal, add its genetic value `nums[j]` to the hash set.
    - d. After collecting all values, find the smallest missing positive integer. Initialize a variable `missingValue = 1`.
    - e. While the hash set contains `missingValue`, increment `missingValue`.
    - f. Store the final `missingValue` in `ans[i]`.
- 5. After iterating through all nodes, return the `ans` array.

## Optimized DFS on the Path Containing Genetic Value 1
This approach is based on a key observation: the smallest missing genetic value for any subtree is `1` unless the subtree contains the genetic value `1`. This insight allows us to optimize the problem by focusing only on the subtrees that contain the value `1`. These are the subtrees rooted at the node with value `1` and all of its ancestors. By processing only this path and its side-branches, we can achieve a linear time solution.
**Time:** O(N). Building the adjacency list is O(N). Finding `oneNode` is O(N). The main part involves traversing up from `oneNode` and collecting values from side branches. Each node in the tree is part of exactly one such branch (or is on the main path). Therefore, each node's value is added to the `seenValues` set exactly once. The total time for all collections is O(N). The `missingValue` pointer only moves forward, and in total, it will be incremented at most N+1 times. Thus, the overall time complexity is linear. · **Space:** O(N). We need O(N) space for the adjacency list, the `ans` array, and the `seenValues` hash set, which can store up to N distinct genetic values. The queue for the iterative traversal can also hold up to O(N) nodes in the worst case.
**Pros:** - Highly efficient with O(N) time complexity, which passes for large inputs.; - The core idea is clever and reduces the problem scope significantly.
**Cons:** - The logic is more complex to understand and implement compared to the brute-force approach.; - It requires careful handling of pointers/indices to traverse up the path and to correctly identify side branches.
### Explanation
The efficiency of this method comes from avoiding redundant computations. We start by recognizing that any subtree that lacks the genetic value `1` will have `1` as its smallest missing value. Therefore, we can initialize our answer array `ans` with all `1`s.

The problem then reduces to finding the correct answer only for the nodes whose subtrees contain the value `1`. These nodes are precisely the node with value `1` (let's call it `oneNode`) and all its ancestors up to the root.

We can find `oneNode` with a single pass through the `nums` array. If `1` is not present in `nums`, all answers are `1`, and we're done. Otherwise, we start an iterative process from `oneNode`, moving up towards the root using the `parents` array.

We maintain a single `HashSet` called `seenValues` that accumulates the genetic values of the subtrees as we move up the path. We also keep track of the `smallest_missing` value, initialized to `1`.

For each `currentNode` on the path from `oneNode` to the root:
1. We expand our set of values. The subtree of `currentNode` includes `currentNode` itself, the subtree of the child we just came from (`prevNode`), and the subtrees of all other children. Since the values from `prevNode`'s subtree are already in `seenValues`, we only need to add `nums[currentNode]` and the values from the subtrees of `currentNode`'s other children (the "side branches").
2. We achieve this by adding `nums[currentNode]` and then for each child of `currentNode` that is not `prevNode`, we perform a DFS to add all values from its subtree into `seenValues`.
3. After updating `seenValues`, we find the new `smallest_missing` value by incrementing it until we find a value not in the set.
4. This value is the answer for `currentNode`, so we set `ans[currentNode]`. 

This process is efficient because each node in the tree is visited and its value is added to the set exactly once, leading to an overall linear time complexity.

```java
import java.util.*;

class Solution {
    public int[] smallestMissingValueSubtree(int[] parents, int[] nums) {
        int n = parents.length;
        List<List<Integer>> children = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            children.add(new ArrayList<>());
        }
        int oneNode = -1;
        for (int i = 0; i < n; i++) {
            if (i != 0) {
                children.get(parents[i]).add(i);
            }
            if (nums[i] == 1) {
                oneNode = i;
            }
        }

        int[] ans = new int[n];
        Arrays.fill(ans, 1);

        if (oneNode == -1) {
            return ans;
        }

        Set<Integer> seenValues = new HashSet<>();
        int missingValue = 1;
        
        int currentNode = oneNode;
        int prevNode = -1;
        
        while (currentNode != -1) {
            // Collect values from the current node and its side branches
            collectSubtree(currentNode, children, nums, seenValues);
            
            while (seenValues.contains(missingValue)) {
                missingValue++;
            }
            ans[currentNode] = missingValue;
            
            // Move up to the parent
            currentNode = parents[currentNode];
        }

        return ans;
    }

    private void collectSubtree(int u, List<List<Integer>> children, int[] nums, Set<Integer> seenValues) {
        // Use a queue for iterative DFS to avoid stack overflow on skewed trees
        Queue<Integer> q = new LinkedList<>();
        q.offer(u);
        seenValues.add(nums[u]);

        while(!q.isEmpty()){
            int node = q.poll();
            for(int child : children.get(node)){
                if(!seenValues.contains(nums[child])){
                    seenValues.add(nums[child]);
                    q.offer(child);
                }
            }
        }
    }
}
```
*Note: The provided code snippet for `collectSubtree` uses an iterative BFS-like traversal to gather values. This is to prevent potential `StackOverflowError` on deep/skewed trees, which a recursive DFS might face. The logic of which nodes to visit is handled in the main loop by only initiating the collection from specific nodes.* The logic in the main loop is slightly different from the description to be more robust. The `collectSubtree` is called on `currentNode` and it traverses the whole subtree. The `seenValues` set ensures that already visited nodes (from a child's subtree on the path) are not re-processed, making it efficient.
### Algorithm
- 1. Build an adjacency list representation of the tree from the `parents` array.
- 2. Find the node `oneNode` that has the genetic value `1`. If no such node exists, the smallest missing value for every subtree is `1`, so return an array filled with `1`s.
- 3. Initialize an answer array `ans` of size `n` with all elements set to `1`. This is the default answer for any subtree that does not contain the value `1`.
- 4. Initialize an empty `HashSet<Integer>` called `seenValues` to store genetic values, and an integer `missingValue` to `1`.
- 5. Traverse upwards from `oneNode` to the root of the tree. Let `currentNode` be the node being processed and `prevNode` be the child on the path we just came from.
- 6. In a loop, while `currentNode` is valid (not -1):
    - a. Add the value `nums[currentNode]` to `seenValues`.
    - b. For each child of `currentNode`, if the child is not `prevNode`, perform a full DFS from that child to collect all genetic values in its subtree and add them to `seenValues`.
    - c. After collecting all new values for the current subtree, update `missingValue` by incrementing it as long as `seenValues` contains the current `missingValue`.
    - d. Set `ans[currentNode] = missingValue`.
    - e. Move up the path: `prevNode = currentNode`, `currentNode = parents[currentNode]`.
- 7. Return the `ans` array.

# Solutions
### Java

```java
class Solution {
private
  List<Integer>[] g;
private
  boolean[] vis;
private
  boolean[] has;
private
  int[] nums;
public
  int[] smallestMissingValueSubtree(int[] parents, int[] nums) {
    int n = nums.length;
    this.nums = nums;
    g = new List[n];
    vis = new boolean[n];
    has = new boolean[n + 2];
    Arrays.setAll(g, i->new ArrayList<>());
    int idx = -1;
    for (int i = 0; i < n; ++i) {
      if (i > 0) {
        g[parents[i]].add(i);
      }
      if (nums[i] == 1) {
        idx = i;
      }
    }
    int[] ans = new int[n];
    Arrays.fill(ans, 1);
    if (idx == -1) {
      return ans;
    }
    for (int i = 2; idx != -1; idx = parents[idx]) {
      dfs(idx);
      while (has[i]) {
        ++i;
      }
      ans[idx] = i;
    }
    return ans;
  }
private
  void dfs(int i) {
    if (vis[i]) {
      return;
    }
    vis[i] = true;
    if (nums[i] < has.length) {
      has[nums[i]] = true;
    }
    for (int j : g[i]) {
      dfs(j);
    }
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> smallestMissingValueSubtree(vector<int> &parents,
                                          vector<int> &nums) {
    int n = nums.size();
    vector<int> g[n];
    bool vis[n];
    bool has[n + 2];
    memset(vis, false, sizeof(vis));
    memset(has, false, sizeof(has));
    int idx = -1;
    for (int i = 0; i < n; ++i) {
      if (i) {
        g[parents[i]].push_back(i);
      }
      if (nums[i] == 1) {
        idx = i;
      }
    }
    vector<int> ans(n, 1);
    if (idx == -1) {
      return ans;
    }
    function<void(int)> dfs = [&](int i) {
      if (vis[i]) {
        return;
      }
      vis[i] = true;
      if (nums[i] < n + 2) {
        has[nums[i]] = true;
      }
      for (int j : g[i]) {
        dfs(j);
      }
    };
    for (int i = 2; ~idx; idx = parents[idx]) {
      dfs(idx);
      while (has[i]) {
        ++i;
      }
      ans[idx] = i;
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def smallestMissingValueSubtree(self, parents: List[int], nums: List[int]) -> List[int]: def dfs(i: int): if vis[i]: return vis[i] = True if nums[i] < len(has): has[nums[i]] = True for j in g[i]: dfs(j) n = len(nums) ans = [1] * n g = [[] for _ in range(n)] idx = - 1 for i, p in enumerate(parents): if i: g[p]. append(i) if nums[i] == 1: idx = i if idx == - 1: return ans vis = [False] * n has = [False] * (n + 2) i = 2 while idx != - 1: dfs(idx) while has[i]: i += 1 ans[idx] = i idx = parents[idx] return ans

```