We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Find Subtree Sizes After Changes

Difficulty: Medium

Problem Description

You are given a tree rooted at node 0 that consists of n nodes numbered from 0 to n - 1. The tree is represented by an array parent of size n, where parent[i] is the parent of node i. Since node 0 is the root, parent[0] == -1. You are also given a string s of length n, where s[i] is the character assigned to node i.

We make the following changes on the tree one time simultaneously for all nodes x from 1 to n - 1:

  • Find the closest node y to node x such that y is an ancestor of x, and s[x] == s[y].
  • If node y does not exist, do nothing.
  • Otherwise, remove the edge between x and its current parent and make node y the new parent of x by adding an edge between them.

Return an array answer of size n where answer[i] is the size of the subtree rooted at node i in the final tree.

Key Insights

  • The tree structure allows us to traverse and determine relationships between nodes.
  • Ancestor relationships can be efficiently tracked using backtracking or depth-first search (DFS).
  • A hashmap can help in quickly finding the closest ancestor with matching characters.
  • Post-processing is required to calculate the size of subtrees after the changes.

Space and Time Complexity

Time Complexity: O(n) - We traverse the tree and perform operations in linear time relative to the number of nodes. Space Complexity: O(n) - We use additional data structures (like arrays or maps) to store parent-child relationships and results.

Solution

To solve this problem, we will use Depth-First Search (DFS) along with a hashmap to track the closest ancestor for each node. The approach involves:

  1. Building the tree from the parent array.
  2. Using DFS to traverse the tree and find the closest ancestor for each node that has the same character.
  3. Adjusting the parent-child relationships based on these ancestors.
  4. Finally, performing another DFS to calculate the size of subtrees for all nodes.

Code Solutions

def findSubtreeSizes(parent, s):
    n = len(parent)
    tree = [[] for _ in range(n)]
    for i in range(1, n):
        tree[parent[i]].append(i)

    # To store the new parent and size of subtree
    new_parent = [-1] * n
    subtree_size = [0] * n

    # Map to track the closest ancestor with the same character
    closest = {}

    def dfs(node):
        # First, process all children
        for child in tree[node]:
            dfs(child)
        
        # Determine the size of the subtree rooted at `node`
        subtree_size[node] = 1  # Count itself
        for child in tree[node]:
            subtree_size[node] += subtree_size[child]

        # Update the closest map for the current node
        if s[node] in closest:
            # We found a matching character
            new_parent[node] = closest[s[node]]
        closest[s[node]] = node  # Update the closest for this character

    # Start DFS from the root
    dfs(0)

    # Calculate the final sizes after changes
    for i in range(n):
        if new_parent[i] != -1:
            subtree_size[new_parent[i]] += subtree_size[i] - 1

    return subtree_size

# Example usage
print(findSubtreeSizes([-1, 0, 0, 1, 1, 1], "abaabc"))  # Output: [6, 3, 1, 1, 1, 1]
← Back to All Questions