Problem Description

You are given a family tree represented as a rooted tree with n nodes numbered from 0 to n - 1, where node 0 is the root. The tree structure is defined by an array parents where parents[i] indicates the parent of node i. Since node 0 is the root, parents[0] == -1.

Each node in the tree has a unique genetic value from the range [1, 10^5]. These genetic values are given in an array nums where nums[i] represents the genetic value of node i. All genetic values in nums are distinct.

Your task is to find, for each node i, the smallest positive genetic value that is missing from the subtree rooted at that node. A subtree rooted at node x includes node x itself and all of its descendants.

Return an array ans of length n where ans[i] is the smallest missing genetic value from the subtree rooted at node i.

For example, if a subtree contains nodes with genetic values [1, 2, 4, 5], then the smallest missing value would be 3. If a subtree contains genetic values [2, 3, 4], then the smallest missing value would be 1.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: The problem involves a tree structure where nodes are connected through parent-child relationships. A tree is a special type of graph (specifically, a connected acyclic graph).

Is it a tree?

• Yes: The problem explicitly states we have a family tree rooted at node 0, with parent-child relationships defined by the parents array. Each node (except the root) has exactly one parent, which confirms this is a tree structure.

DFS

• According to the flowchart, when we have a tree structure, the natural algorithm choice is DFS (Depth-First Search).

Conclusion: The flowchart suggests using DFS for this problem. This makes sense because:

1. We need to explore subtrees (which requires traversing from each node to all its descendants)
2. For each node, we need to collect information about all genetic values present in its subtree
3. DFS is ideal for tree traversal where we need to process complete subtrees before returning results to parent nodes
4. The solution requires us to traverse from specific nodes (like the node with genetic value 1) upward to the root, collecting subtree information along the way

The DFS pattern is particularly effective here as we can:

• Traverse the subtree rooted at each node to identify which genetic values are present
• Mark visited nodes to avoid redundant processing
• Efficiently find the smallest missing genetic value by tracking which values appear in each subtree

Intuition

The key insight is that since all genetic values are unique and we're looking for the smallest missing value, most nodes will have an answer of 1 - unless their subtree contains the genetic value 1.

Think about it: if a subtree doesn't contain genetic value 1, then 1 is the smallest missing value for that subtree. This means we only need to do complex calculations for nodes whose subtrees contain 1.

So where is genetic value 1? Since each value appears exactly once, there's only one node with genetic value 1. Let's call this node idx. Now, only the nodes on the path from idx to the root can possibly have subtrees containing 1 (because idx is in their subtree). All other nodes will have answer 1.

For the nodes on the path from idx to root, we need to find the actual smallest missing value. Here's where it gets clever:

1. Start at node idx and use DFS to mark all genetic values present in its subtree
2. Find the smallest positive integer not in this set - this is the answer for node idx
3. Move to the parent of idx and repeat

The brilliant optimization is that as we move up the tree, we don't need to restart from scratch. Each parent's subtree contains all the genetic values from its children's subtrees plus potentially more from other branches. So we can keep accumulating the genetic values we've seen and continue our search for the smallest missing value from where we left off.

For example, if node idx has smallest missing value 5, then its parent's smallest missing value must be at least 5 (since the parent's subtree contains everything idx's subtree has). This means we can start checking from 5 instead of from 1 again.

This approach is efficient because:

• We only do expensive DFS traversals for nodes on one path (from the node with value 1 to root)
• We reuse information as we move up the tree
• The smallest missing value can only increase as we go up (never decrease)

Learn more about Tree, Depth-First Search, Union Find and Dynamic Programming patterns.

Solution Approach

The implementation follows the intuition by focusing on the path from the node containing genetic value 1 to the root:

1. Initialize Data Structures:

• Create an answer array ans initialized with all 1s (since most nodes will have answer 1)
• Build an adjacency list g to represent the tree structure from the parent array
• Find the node idx that has genetic value 1 (if no such node exists, all answers remain 1)

2. Set Up Tracking Arrays:

• vis[i]: Boolean array to track visited nodes during DFS to avoid revisiting
• has[i]: Boolean array where has[i] = True means genetic value i exists in the current subtree being explored
• Initialize a counter i = 2 to track the next potential missing value

3. DFS Function:

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)

This function marks node i as visited, records its genetic value in has, and recursively visits all children.

4. Main Algorithm: Starting from node idx (the node with genetic value 1), traverse up to the root:

while idx != -1:
    dfs(idx)           # Mark all genetic values in subtree rooted at idx
    while has[i]:      # Find smallest missing value starting from i
        i += 1
    ans[idx] = i       # Set the answer for current node
    idx = parents[idx] # Move to parent

Key Optimizations:

• The variable i is never reset - it only increases. This works because as we move up the tree, the smallest missing value can only stay the same or increase (parent subtrees contain all values from child subtrees)
• We only visit each node once across all DFS calls due to the vis array
• The has array accumulates genetic values as we move up, so we don't lose information from previous subtrees

Time Complexity: O(n) where n is the number of nodes, since each node is visited at most once during all DFS traversals combined.

Space Complexity: O(n) for the adjacency list, visited array, and has array.

The algorithm efficiently solves the problem by recognizing that only nodes on one specific path (from the node with value 1 to root) need detailed computation, while all other nodes have a trivial answer of 1.

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Example Input:

• parents = [-1, 0, 0, 1, 1, 2]
• nums = [5, 4, 1, 3, 6, 2]

This creates the following tree:

       0 (val=5)
      / \
     1   2
    / \   \
   3   4   5
(val=4)(val=3)(val=6)(val=2)

Step 1: Initialize

• ans = [1, 1, 1, 1, 1, 1] (all nodes start with answer 1)
• Build adjacency list: g = {0: [1,2], 1: [3,4], 2: [5], 3: [], 4: [], 5: []}
• Find node with value 1: idx = 2 (since nums[2] = 1)

Step 2: Process path from node 2 to root

We'll traverse: node 2 → node 0 (root)

Processing Node 2:

• Start DFS from node 2
• Visit node 2: mark has[1] = True (value 1)
• Visit child node 5: mark has[2] = True (value 2)
• Current has = [False, True, True, False, False, ...]
• Start checking from i = 2: has[2] is True, increment to 3
• Check i = 3: has[3] is False
• ans[2] = 3 (smallest missing value is 3)
• Move to parent: idx = 0

Processing Node 0 (root):

• Continue DFS from node 0 (accumulating previous values)
• Visit node 0: mark has[5] = True (value 5)
• Visit child node 1: mark has[4] = True (value 4)
• Visit grandchild node 3: mark has[3] = True (value 3)
• Visit grandchild node 4: mark has[6] = True (value 6)
• Current has = [False, True, True, True, True, True, True, ...]
• Continue checking from i = 3: all of 3, 4, 5, 6 are True
• Check i = 7: has[7] is False
• ans[0] = 7 (smallest missing value is 7)
• Move to parent: idx = -1 (done, as 0 is the root)

Final Result: ans = [7, 1, 3, 1, 1, 1]

Verification:

• Node 0's subtree has values [5,4,1,3,6,2] → missing 7 ✓
• Node 1's subtree has values [4,3,6] → missing 1 ✓
• Node 2's subtree has values [1,2] → missing 3 ✓
• Node 3's subtree has values [3] → missing 1 ✓
• Node 4's subtree has values [6] → missing 1 ✓
• Node 5's subtree has values [2] → missing 1 ✓

The key insight illustrated here: only nodes 2 and 0 (on the path from the node with value 1 to root) needed detailed computation. All other nodes simply have answer 1 because their subtrees don't contain the value 1.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The algorithm performs a depth-first search starting from the node containing value 1 and traversing up to the root. Key observations:

1. The while loop that finds idx (node with value 1) runs at most once through all nodes: O(n)
2. The main while loop traverses from the node with value 1 up to the root, visiting at most n nodes along the path
3. The DFS function dfs(i) visits each node at most once due to the vis[i] check. Across all DFS calls, every node is visited exactly once: O(n) total
4. The inner while loop while has[i]: i += 1 increments i from 2 to at most n+1. Since i never decreases, this contributes O(n) total across all iterations

Therefore, the total time complexity is O(n) + O(n) + O(n) = O(n).

Space Complexity: O(n)

The algorithm uses the following data structures:

1. ans: array of size n storing the result: O(n)
2. g: adjacency list representation of the tree with n nodes: O(n)
3. vis: boolean array of size n for tracking visited nodes: O(n)
4. has: boolean array of size n+2 for tracking which values exist in subtrees: O(n)
5. Recursive call stack for DFS: In the worst case (skewed tree), the depth can be O(n)

The total space complexity is O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Assumption About Value Range

Pitfall: A common mistake is assuming that genetic values are limited to the range [1, n] where n is the number of nodes. The problem states values can be up to 10^5, which may be larger than n.

Example Issue:

# Incorrect: assumes values are bounded by n
value_exists = [False] * (n + 2)  # This could cause index out of bounds!

# When marking values:
if nums[node] < len(value_exists):  # This check prevents crashes but silently ignores large values
    value_exists[nums[node]] = True

Solution: Size the value_exists array based on the maximum possible genetic value:

# Correct approach:
max_value = 10**5 + 2  # Based on problem constraints
value_exists = [False] * max_value

# Or dynamically based on actual values:
max_genetic_value = max(nums)
value_exists = [False] * (max_genetic_value + 2)

2. Resetting the Missing Value Counter

Pitfall: Developers might instinctively reset current_missing back to 1 or 2 for each node on the path, thinking each subtree needs independent computation.

Example Issue:

while current_node != -1:
    current_missing = 2  # WRONG: Resetting for each node
    mark_subtree_values(current_node)
    while value_exists[current_missing]:
        current_missing += 1
    result[current_node] = current_missing
    current_node = parents[current_node]

Why It's Wrong: As we move up the tree, parent nodes contain all values from their children's subtrees. The smallest missing value can only increase or stay the same - it never decreases. Resetting would cause unnecessary recomputation and incorrect results.

Solution: Keep current_missing persistent across iterations:

current_missing = 2  # Initialize once outside the loop
while current_node != -1:
    # Don't reset current_missing here
    mark_subtree_values(current_node)
    while value_exists[current_missing]:
        current_missing += 1
    result[current_node] = current_missing
    current_node = parents[current_node]

3. Building the Tree Structure Incorrectly

Pitfall: Confusing parent-to-child vs child-to-parent relationships when building the adjacency list.

Example Issue:

# Incorrect: Adding parent to child's list
for node_id, parent_id in enumerate(parents):
    if node_id > 0:
        children[node_id].append(parent_id)  # WRONG direction!

Solution: Ensure you're adding children to their parent's adjacency list:

# Correct: Adding child to parent's list
for node_id, parent_id in enumerate(parents):
    if node_id > 0:  # Skip root (parent_id would be -1)
        children[parent_id].append(node_id)

4. Not Handling the Case When Value 1 Doesn't Exist

Pitfall: Forgetting to handle the edge case where no node has genetic value 1, leading to attempting to traverse from a non-existent node.

Example Issue:

# Find node with value 1
node_with_value_one = -1
for i, val in enumerate(nums):
    if val == 1:
        node_with_value_one = i
        break

# Forgetting to check if it was found
current_node = node_with_value_one  # Could be -1
while current_node != -1:  # This would immediately exit without processing anything
    # ...

Solution: Explicitly check and handle this case:

if node_with_value_one == -1:
    # All subtrees are missing value 1
    return result  # result is already initialized with all 1s