Watch 7 video solutions for Smallest Missing Genetic Value in Each Subtree, a hard level problem involving Dynamic Programming, Tree, Depth-First Search. This walkthrough by Happy Coding has 1,533 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
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:
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.length2 <= n <= 1050 <= parents[i] <= n - 1 for i != 0parents[0] == -1parents represents a valid tree.1 <= nums[i] <= 105nums[i] is distinct.Problem Overview: You are given a rooted tree where each node has a unique genetic value. For every node, compute the smallest positive genetic value that does not appear in its subtree. The challenge is efficiently tracking which values exist inside each subtree without recomputing sets from scratch.
Approach 1: DFS with a Set to Track Genetic Values (O(n^2) worst-case time, O(n) space)
This method performs a depth-first search and builds a set of genetic values for each subtree. When DFS visits a node, it recursively collects the sets from its children and merges them into the current node’s set. After merging, iterate from value 1 upward until you find the smallest number not present in the set. That value becomes the answer for the current node. The key operation is merging child sets and performing hash lookups to detect missing values. This approach is easy to implement and clearly demonstrates subtree aggregation, but repeated set merges can degrade to O(n^2) time in skewed trees.
Approach 2: Union-Find with Path Compression (O(n α(n)) time, O(n) space)
This optimized strategy uses a Union-Find structure combined with subtree traversal. The core observation: only nodes along the path from the node containing genetic value 1 up to the root can have answers greater than 1. All other subtrees are missing value 1. Starting from the node that contains value 1, move upward toward the root while progressively marking nodes in each subtree as visited using DFS. Each visited genetic value is unioned with the next value, effectively tracking the next available missing integer using path compression. The smallest missing value for the current subtree is found by querying the next unconnected number. This avoids rebuilding sets and ensures near-linear complexity.
The solution heavily relies on properties of tree traversal. Subtrees can be explored independently, and the genetic value constraint allows efficient detection of missing integers once values are marked.
Recommended for interviews: The Union-Find optimization is the approach most interviewers expect for this Hard problem. It demonstrates deeper insight into subtree structure and missing-number tracking. Implementing the DFS + set approach first can show your reasoning process, but the optimized Union-Find method proves you can reduce redundant work and reach near-linear complexity.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| DFS with Set Tracking | O(n^2) worst case | O(n) | Good for understanding subtree aggregation and quick prototyping |
| Union-Find with Path Compression | O(n α(n)) | O(n) | Optimal solution for large trees and interview settings |