Smallest Missing Genetic Value In Each Subtree - Leetcode Solution

Problem Statement: Given an array of n unique integers where each integer represents the genetic value of a node in a binary tree with n nodes. Each ancestor/descendant pair of nodes has connected genetic values in the tree. Return an array representing the subtree where the smallest genetic value is missing from each subtree.

Example: Input: nums = [1,2,3,4,5,6,7] Output: [-1, 1, -1, 1, 3, 6, -1]

Explanation: The tree is shown below: 1 /
2 3 / \ /
4 5 6 7 The smallest missing genetic value in each subtree is shown below: -1 /
1 -1 / \ /
1 -1 3 -1

Approach: We need to traverse the binary tree in a post-order manner and for each node, we will calculate the smallest missing genetic value in its subtree. To do this, we will keep a set of all genetic values present in the current node's subtree. Then we will loop through all the genetic values from the minimum to the maximum value and for the first missing value, we will store it in the current node's index in the output array.

Algorithm:

1. Initialize a dictionary parent with keys as all the genetic values and values as an empty list.
2. Traverse the tree in postorder fashion and call dfs function with node's value and a set containing the values of all the nodes in the subtree rooted at given node.
3. In the dfs function, if the current node is None, we will return an empty set.
4. We will recurse on left and right subtree and get the sets l and r respectively.
5. Then we will join the set {val} representing the current node's value and the sets l and r and store it in set s.
6. Add the current node's value to the parent dictionary as a key and append the current node to the corresponding value's list.
7. Loop from the minimum to the maximum value in the set s and find the first missing genetic value.
8. Store the missing genetic value in ans[current_node's index] if it is greater than the current node value.
9. Return the set s.

Code:

class Solution: def smallestMissingValueSubtree(self, nums: List[int], edges: List[List[int]], indices: List[int]) -> List[int]: parent = {i:[] for i in range(1, max(nums)+1)} for u, v in edges: parent[v].append(u) ans = [-1]*len(nums)

    def dfs(node, s):
        if not node:
            return set()
        l = dfs(parent[node][0], s)
        r = dfs(parent[node][1], s)
        s |= {node} | l | r
        parent[node].append(s)
        for i in range(min(s), max(s)+2):
            if i not in s:
                ans[indices[node-1]] = i
                break
        return s
    
    dfs(edges[-1][1], set())
    return ans

Time Complexity: O(nlogn) Space Complexity: O(n)

1