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

Maximum Subtree of the Same Color

Number: 3304

Difficulty: Medium

Paid? Yes

Companies: Microsoft

Problem Description

Given a tree (an acyclic connected graph) with n nodes (numbered from 0 to n-1) represented by a list of edges, and an array colors where colors[i] denotes the color of node i, find a node v such that every node in the subtree of v has the same color. Return the maximum number of nodes among these subtrees.

Key Insights

  • The tree is processed using Depth-First Search (DFS) since each node’s property (whether its subtree is homogeneous) depends on the properties of its children.
  • For a node to have a homogeneous subtree, every one of its children must have a homogeneous subtree with the same color as the parent.
  • A global variable can be maintained to keep track of the maximum subtree size encountered that is homogeneous.
  • Use an adjacency list to represent the tree given the edge list.

Space and Time Complexity

Time Complexity: O(n) – Each node is visited exactly once. Space Complexity: O(n) – The recursion stack and the adjacency list can both take O(n) space.

Solution

We approach the problem with a recursive DFS. We first build an adjacency list from the given edge list. Then for each node during the DFS, we check whether all its children have a homogeneous subtree that shares the same color as the node itself. If so, the size of the subtree rooted at that node will be 1 (for the node itself) plus the sizes of all the homogeneous subtrees of its children. Otherwise, that node does not qualify as having a homogeneous subtree (and we denote this by returning a marker value such as -1). At every node that qualifies, we update a global maximum subtree size variable. This ensures that by the end of DFS, we have the size of the largest subtree where every node has the same color.

Code Solutions

# Build the tree using an adjacency list and perform DFS
def maximumSubtreeSameColor(edges, colors):
    from collections import defaultdict
    # Build adjacency list
    n = len(colors)
    tree = defaultdict(list)
    for u, v in edges:
        tree[u].append(v)
        tree[v].append(u)

    # Global variable to track maximum size of homogeneous subtree
    max_subtree = [0]  # Use list to modify inside nested function

    # DFS function returns the size of subtree if homogeneous, otherwise -1
    def dfs(node, parent):
        # Start with current node count = 1, assume it is initially homogeneous
        size = 1
        is_homogeneous = True
        
        # Explore children (neighbors except the parent)
        for child in tree[node]:
            if child == parent:
                continue
            childSubtreeSize = dfs(child, node)
            # If the child's subtree is not homogeneous or its color differs from current node, mark false
            if childSubtreeSize == -1 or colors[child] != colors[node]:
                is_homogeneous = False
            else:
                size += childSubtreeSize
        
        # Update the global maximum if the current subtree is homogeneous
        if is_homogeneous:
            max_subtree[0] = max(max_subtree[0], size)
            return size
        else:
            return -1

    dfs(0, -1)  # Start DFS from root node 0 with no parent
    return max_subtree[0]

# Example usage:
#print(maximumSubtreeSameColor([[0,1],[0,2],[0,3]], [1,1,2,3]))
← Back to All Questions