#2003

Hard

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

Smallest Missing Genetic Value in Each Subtree

Determine the smallest missing genetic value in each subtree using binary-tree traversal and precise state tracking efficiently.

dynamic programming tree depth first search union find

Problem Statement

You are given a tree rooted at node 0 with n nodes numbered from 0 to n - 1. The parent relationship is described by a 0-indexed array parents where parents[i] indicates the parent of node i, and parents[0] == -1 for the root. Each node i also has a unique genetic value given in the array nums, where 1 <= nums[i] <= 105.

Your task is to compute an array ans of length n such that ans[i] is the smallest positive integer not present in the subtree rooted at node i. A subtree includes the node itself and all its descendants. Efficiently determining these missing values requires combining depth-first traversal with careful merging of subtree information.

Examples

Example 1

Input: parents = [-1,0,0,2], nums = [1,2,3,4]

Output: [5,1,1,1]

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]

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]

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.

Solution Approach

DFS With Set Tracking

Perform a depth-first search starting at the root. For each node, maintain a set of genetic values seen in its subtree. Merge child sets into the parent set to track all numbers efficiently, and identify the smallest missing integer by checking sequentially from 1 upwards.

Optimized Smallest Missing Propagation

If a subtree does not contain 1, then the smallest missing value is always 1. Use this observation to skip unnecessary merging for nodes whose subtrees do not reach the minimal values. Only propagate the sets upwards for nodes that may influence the missing number calculation.

Union-Find Inspired Merging

For large trees, merge smaller child sets into larger parent sets to reduce memory copying. Track the current minimal missing genetic value at each node as you merge, updating it efficiently to avoid rechecking every element each time.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity depends on the DFS traversal and merging strategy; naive merging is O(n^2) but optimized union-by-size approaches reduce it near O(n). Space complexity is proportional to the number of nodes and distinct genetic values in the largest subtree.

What Interviewers Usually Probe

Ask about handling missing value propagation efficiently across subtrees.
Expect discussion on how to optimize set merging for large trees.
Look for recognizing that missing value 1 can be directly returned when absent from a subtree.

Common Pitfalls or Variants

Common pitfalls

Merging child sets without optimizing leads to TLE for large n.
Assuming missing values propagate sequentially without checking each subtree's minimal value.
Ignoring the special case when 1 is missing, causing incorrect results in many leaf subtrees.

Follow-up variants

Find the largest missing genetic value in each subtree instead of the smallest.
Compute the sum of all missing genetic values in each subtree.
Determine missing genetic values for arbitrary subtrees queried multiple times dynamically.

FAQ

What is the simplest way to find the smallest missing genetic value in each subtree?

Use DFS with set tracking for each subtree, then merge child sets to the parent while checking for the smallest missing integer.

Why is checking for 1 first important in this problem?

If 1 is missing in a subtree, it is guaranteed to be the smallest missing value, simplifying the computation for that node.

Can union-find techniques optimize this problem?

Yes, merging smaller child sets into larger parent sets reduces redundant copying and speeds up the missing value computation.

How do you handle large trees without exceeding memory limits?

Track only necessary elements and merge sets smartly, avoiding storing full sets for every node simultaneously.

Does this problem pattern always require DFS?

Yes, binary-tree traversal with DFS is essential to aggregate subtree information and compute missing genetic values correctly.

terminal

Solution

Solution 1: 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$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

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

Continue Practicing

#2368 reachable nodes with restrictions #1569 number of ways to reorder array to get same bst #1483 kth ancestor of a tree node