Skip to main content
Talentd

Smallest Missing Genetic Value in Each Subtree - Solution & Explanation

HardDynamic ProgrammingTreeDepth-First SearchUnion Find18 min read
Practice this problem

Problem Statement

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.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.

Approach Overview

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 1: DFS with a Set to Track Genetic Values

This approach utilizes depth-first search (DFS) to traverse the tree and a set to track genetic values in each subtree. By doing this, you can efficiently identify the smallest missing genetic value.

The code employs DFS to explore each subtree and gather genetic values using a set. The aim is to determine the smallest missing genetic value in each subtree by iterating through possible genetic numbers and checking their presence.

Code

PythonC++

Python

C++

Complexity

The time complexity is O(n^2), predominantly due to the iterative process over the genetic values up to n+1 in each subtree DFS traversal. The space complexity is O(n) utilized by the data structures to track children and visited nodes.

Try this approach in the editor →

Approach 2: Union-Find with Path Compression

This method uses a union-find data structure with path compression to efficiently detect the smallest missing genetic value. It focuses on connectivity and quick access to elements in subtrees.

This Java code integrates a DFS traversal with a union-find approach to efficiently trace and flag seen genetic values using an array. This assists in promptly identifying the smallest missing number.

Code

JavaC#

Java

C#

Complexity

The time complexity is O(n log n) due to union-find operations with path compression, while space complexity is also O(n) due to auxiliary storage usage.

Try this approach in the editor →

Approach 3: DFS

We notice that each node has a unique gene value, so we only need to find the node idx with gene value 1, and all nodes except for those on the path from node idx to the root node 0 have an answer of 1.

Therefore, we initialize the answer array ans to [1,1,...,1], and our focus is on finding the answer for each node on the path from node idx to the root node 0.

We can start from node idx and use depth-first search to mark the gene values that appear in the subtree rooted at idx, and record them in the array has. During the search process, we use an array vis to mark the visited nodes to prevent repeated visits.

Next, we start from i=2 and keep looking for the first gene value that has not appeared, which is the answer for node idx. Here, i is strictly increasing, because the gene values are unique, so we can always find a gene value that has not appeared in [1,..n+1].

Then, we update the answer for node idx, i.e., ans[idx]=i, and update idx to its parent node to continue the above process until idx=-1, which means we have reached the root node 0.

Finally, we return the answer array ans.

The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
DFS with a Set to Track Genetic Values

The time complexity is O(n^2), predominantly due to the iterative process over the genetic values up to n+1 in each subtree DFS traversal. The space complexity is O(n) utilized by the data structures to track children and visited nodes.

Union-Find with Path Compression

The time complexity is O(n log n) due to union-find operations with path compression, while space complexity is also O(n) due to auxiliary storage usage.

DFS—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
DFS with Set TrackingO(n^2) worst caseO(n)Good for understanding subtree aggregation and quick prototyping
Union-Find with Path CompressionO(n α(n))O(n)Optimal solution for large trees and interview settings

Video Solution

LeetCode 2003. Smallest Missing Genetic Value in Each Subtree • Happy Coding • 1,563 views views

Watch 4 more video solutions →

Frequently Asked Questions

Is Smallest Missing Genetic Value in Each Subtree easy or hard?
LeetCode classifies this problem as Hard because it combines tree traversal, missing-number tracking, and optimization techniques. The naive DFS approach is straightforward, but achieving near-linear time requires deeper insight using Union-Find and subtree observations.
Smallest Missing Genetic Value in Each Subtree Python/Java solution
Python and C++ implementations typically use DFS with sets or optimized traversal logic. Java and C# solutions often use Union-Find structures to track the next available missing genetic value. All implementations rely on subtree traversal and efficient value tracking.
How to solve Smallest Missing Genetic Value in Each Subtree in O(n)?
Use the observation that only nodes on the path from the node containing genetic value 1 to the root can have answers greater than 1. Traverse this path upward, perform DFS to mark values in each subtree, and maintain the smallest missing number using Union-Find or a pointer that skips already-seen values. This ensures each node and value is processed once.
What is the best approach for Smallest Missing Genetic Value in Each Subtree?
The most efficient approach uses Union-Find with path compression combined with DFS traversal. The algorithm starts from the node containing genetic value 1 and moves upward toward the root while marking subtree values as visited. This avoids rebuilding sets for every subtree and achieves near-linear time complexity of O(n α(n)).
Is Smallest Missing Genetic Value in Each Subtree asked at Google/Amazon/Meta?
Tree and union-find problems with subtree queries frequently appear in interviews at companies like Google, Amazon, and Meta. Variants of missing-number tracking in trees and DFS aggregation are common in system design and algorithm rounds.
What data structure is used in Smallest Missing Genetic Value in Each Subtree?
Key data structures include adjacency lists for representing the tree, hash sets for tracking genetic values in simpler solutions, and Union-Find with path compression for the optimal implementation. DFS traversal is used to explore each subtree efficiently.
What is the time complexity of Smallest Missing Genetic Value in Each Subtree?
The optimal solution runs in O(n α(n)) time using Union-Find with path compression, where α(n) is the inverse Ackermann function and effectively constant. A simpler DFS approach that merges sets can degrade to O(n^2) in the worst case due to repeated set merging.

Ready to solve this problem?

Practice Smallest Missing Genetic Value in Each Subtree with our built-in code editor and test cases.

Practice on FleetCode
Previous

Longest Palindromic Substring

Next

Regular Expression Matching