Maximum Subtree of the Same Color #3 Most Asked

Medium

2 views

Topics:

TreesGraphsRecursionDynamic Programming

You are given a tree with n nodes labeled from 0 to n - 1. Each node has a color represented by an integer in the array colors of length n, where colors[i] is the color of the i^th node.

You are also given a 2D array edges of size n - 1, where each edges[i] = [u_i, v_i] represents an undirected edge connecting nodes u_i and v_i.

A subtree is considered to be of the same color if all nodes in the subtree have the same color. Return the size of the largest subtree of the same color.

Example 1:

Input: n = 5, colors = [0,1,1,3,0], edges = [[0,1],[0,2],[1,3],[2,4]]
Output: 2
Explanation:
- Subtree 0 contains nodes [0,1,2,3,4] and has colors [0,1,1,3,0], so it is not of the same color.
- Subtree 1 contains nodes [1,3] and has colors [1,3], so it is not of the same color.
- Subtree 2 contains nodes [2,4] and has colors [1,0], so it is not of the same color.
- Subtree 3 contains node [3] and has color [3], so it is of the same color with size 1.
- Subtree 4 contains node [4] and has color [0], so it is of the same color with size 1.
Only subtrees 3 and 4 have the same color (3 and 0, respectively), and their sizes are both 1. Thus, the answer is 1.

Example 2:

Input: n = 5, colors = [0,0,0,0,0], edges = [[0,1],[0,2],[1,3],[2,4]]
Output: 5
Explanation:
Since all nodes have the same color, the subtree containing all the nodes is of the same color, so the answer is 5.

Constraints:

1 <= n <= 10⁵
0 <= colors[i] <= 10⁵
edges.length == n - 1
edges[i].length == 2
0 <= u_i, v_i < n
The input is generated such that edges represents a valid tree.

Try coding it in LeetCode

Maximum Subtree of the Same Color #3 Most Asked

Medium

BlackRock

2 views

Topics:

TreesGraphsRecursionDynamic Programming

You are given a tree with n nodes labeled from 0 to n - 1. Each node has a color represented by an integer in the array colors of length n, where colors[i] is the color of the i^th node.

You are also given a 2D array edges of size n - 1, where each edges[i] = [u_i, v_i] represents an undirected edge connecting nodes u_i and v_i.

A subtree is considered to be of the same color if all nodes in the subtree have the same color. Return the size of the largest subtree of the same color.

Example 1:

Input: n = 5, colors = [0,1,1,3,0], edges = [[0,1],[0,2],[1,3],[2,4]]
Output: 2
Explanation:
- Subtree 0 contains nodes [0,1,2,3,4] and has colors [0,1,1,3,0], so it is not of the same color.
- Subtree 1 contains nodes [1,3] and has colors [1,3], so it is not of the same color.
- Subtree 2 contains nodes [2,4] and has colors [1,0], so it is not of the same color.
- Subtree 3 contains node [3] and has color [3], so it is of the same color with size 1.
- Subtree 4 contains node [4] and has color [0], so it is of the same color with size 1.
Only subtrees 3 and 4 have the same color (3 and 0, respectively), and their sizes are both 1. Thus, the answer is 1.

Example 2:

Input: n = 5, colors = [0,0,0,0,0], edges = [[0,1],[0,2],[1,3],[2,4]]
Output: 5
Explanation:
Since all nodes have the same color, the subtree containing all the nodes is of the same color, so the answer is 5.

Constraints:

1 <= n <= 10⁵
0 <= colors[i] <= 10⁵
edges.length == n - 1
edges[i].length == 2
0 <= u_i, v_i < n
The input is generated such that edges represents a valid tree.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of possible values for the node colors, and can the target color fall outside this range?
Can the tree be empty, or can a node have a null left or right child, and what should be returned in those cases?
If multiple subtrees of the same maximum size exist and match the target color, can I return the size of any one of them?
What data type is used to represent the tree nodes, and can I assume it's a standard tree node structure with 'left', 'right', and 'color' attributes?
Are node colors represented as integers, and if so, are negative color values possible?

Brute Force Solution

Approach

The brute force method to find the largest subtree of the same color involves checking every possible subtree. We essentially explore all combinations of nodes and their descendants to see if they form a valid subtree of the desired color. This exhaustive search guarantees that we will find the maximum subtree.

Here's how the algorithm would work step-by-step:

Start by considering each node in the tree as a potential root of a subtree.
For each node (potential subtree root), check if the color of that node matches the color we are looking for.
If the colors match, consider that node and all of its descendants as a potential subtree.
Verify that every node within this potential subtree has the same color as the root node.
If they all have the same color, record the size of this subtree (the number of nodes).
Repeat this process for every node in the tree.
After checking all possible subtrees, compare the sizes of all the subtrees you recorded.
The largest subtree you found is the answer.

Code Implementation

def maximum_subtree_same_color_brute_force(graph, node_colors):
    max_subtree_size = 0

    for start_node in graph:
        # Start a depth-first search from each node
        subtree_nodes = [start_node]
        subtree_color = node_colors[start_node]
        current_subtree_size = 1

        max_subtree_size = max(max_subtree_size, current_subtree_size)

        nodes_to_explore = [start_node]

        while nodes_to_explore:
            current_node = nodes_to_explore.pop(0)

            for neighbor in graph[current_node]:
                # Avoid cycles and only explore same-color neighbors.
                if neighbor not in subtree_nodes and node_colors[neighbor] == subtree_color:

                    subtree_nodes.append(neighbor)
                    nodes_to_explore.append(neighbor)
                    current_subtree_size += 1

                    max_subtree_size = max(max_subtree_size, current_subtree_size)

    return max_subtree_size

Big(O) Analysis

Time Complexity

O(n^2) – The algorithm iterates through each of the n nodes in the tree to consider it as a potential root of a subtree. For each potential root, it then checks all of its descendants to verify if they have the same color as the root, which in the worst case could involve traversing a significant portion of the tree, potentially visiting all n nodes. Therefore, the nested operation of checking each node as a root and then validating its descendants leads to a time complexity of approximately n * n. Thus the overall time complexity is O(n^2).

Space Complexity

O(N) – The brute force solution, as described, involves a recursive check to verify if a subtree rooted at each node has the same color. In the worst-case scenario, this recursion could traverse the entire tree from the root to a leaf, leading to a maximum recursion depth of N, where N is the number of nodes in the tree. Each recursive call adds a new frame to the call stack. Therefore, the auxiliary space required for the recursion stack can grow linearly with the number of nodes. This results in a space complexity of O(N).

Optimal Solution

Approach

The most efficient approach involves exploring the tree structure in a specific order to determine the largest possible subtree. We utilize a method where information is passed upwards from the leaves to the root, allowing us to make informed decisions about subtree size.

Here's how the algorithm would work step-by-step:

Begin by examining the smallest parts of the tree: the leaves. These are the starting points for calculating subtree sizes.
For each leaf, check if its color matches the desired color. If it does, its subtree size is one; otherwise, it's zero.
Move upwards in the tree to the parent nodes. For each parent, check its color.
If the parent's color matches the desired color, add the sizes of all its children's subtrees to get its potential subtree size. If the parent's color doesn't match, its subtree size is zero.
Continue this process, moving up the tree level by level. At each node, the subtree size is either zero (if its color doesn't match) or the sum of its children's subtree sizes plus one (for the node itself).
Keep track of the largest subtree size encountered during this upward traversal.
Once you reach the root of the tree, the largest subtree size recorded is the answer: the size of the maximum subtree with the desired color.

Code Implementation

def maximum_same_color_subtree(node, colors):
    max_subtree_size = 0

    def dfs(current_node):
        nonlocal max_subtree_size
        subtree_size = 1
        is_same_color = True

        for child in current_node.children:
            child_subtree_size, child_same_color = dfs(child)

            # Propagate color consistency upwards.
            if not child_same_color or colors[child.val] != colors[current_node.val]:
                is_same_color = False
            else:
                subtree_size += child_subtree_size

        if is_same_color:
            # Update max size if the subtree has the same color.
            max_subtree_size = max(max_subtree_size, subtree_size)
        else:
            max_subtree_size = max(max_subtree_size, 1)

        return subtree_size, is_same_color

    dfs(node)
    return max_subtree_size

class Node:
    def __init__(self, val):
        self.val = val
        self.children = []

def create_tree(edges, colors, root_val):
    nodes = {}
    for i in range(len(colors)):
        nodes[i] = Node(i)
    root = nodes[root_val]

    for parent, child in edges:
        nodes[parent].children.append(nodes[child])

    return root

# Example Usage (Test case 1)
# colors = [0, 0, 0, 1, 1]
# edges = [[0, 1], [0, 2], [1, 3], [1, 4]]
# root_val = 0
# root = create_tree(edges, colors, root_val)
# result = maximum_same_color_subtree(root, colors)
# print(result)  # Output: 3

# Example Usage (Test case 2)
# colors = [0, 1, 0, 1, 1]
# edges = [[0, 1], [0, 2], [1, 3], [1, 4]]
# root_val = 0
# root = create_tree(edges, colors, root_val)
# result = maximum_same_color_subtree(root, colors)
# print(result) # Output 1

# Example Usage (Test case 3)
# colors = [0, 0, 0, 0, 0]
# edges = [[0, 1], [0, 2], [1, 3], [1, 4]]
# root_val = 0
# root = create_tree(edges, colors, root_val)
# result = maximum_same_color_subtree(root, colors)
# print(result) # Output 5

# Example Usage (Test case 4)
# colors = [1,1,1,1,1,0,0,0,0]
# edges = [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6],[5,7],[5,8]]
# root_val = 0
# root = create_tree(edges, colors, root_val)
# result = maximum_same_color_subtree(root, colors)
# print(result) # Output 5

Big(O) Analysis

Time Complexity

O(n) – The algorithm traverses the tree in a bottom-up fashion, visiting each node exactly once. At each node, it performs a constant amount of work: checking the node's color and summing the subtree sizes of its children. Since each node is visited and processed only once, the time complexity is directly proportional to the number of nodes in the tree, n. Therefore, the overall time complexity is O(n).

Space Complexity

O(H) – The space complexity is determined primarily by the recursion depth of the tree traversal. In the worst-case scenario, the tree is highly skewed, resembling a linked list, resulting in a recursion depth of H, where H is the height of the tree. The call stack would then store H function call frames. Therefore, the auxiliary space used is proportional to the tree's height, H.

Edge Cases

Case	How to Handle
Null or empty tree	Return 0 immediately as there are no nodes to form a subtree.
Tree with only one node and it matches the target color	Return 1, representing the size of the single-node subtree.
Tree with only one node and it does not match the target color	Return 0, indicating no valid subtree.
All nodes in the tree have the target color	Return the total number of nodes in the tree.
No nodes in the tree have the target color	Return 0, indicating no valid subtree.
Large tree to ensure the solution is scalable and does not cause stack overflow in recursive solutions	Iterative approaches using stacks or queues can prevent stack overflow for very deep trees; consider using that approach.
Skewed tree (e.g., a linked list structure)	Handle the skewed structure efficiently without unnecessary traversal of nonexistent branches.
Target color is negative or zero	The solution must correctly handle any valid integer color value.

Null or empty tree

How to Handle:

Return 0 immediately as there are no nodes to form a subtree.

Tree with only one node and it matches the target color

How to Handle:

Return 1, representing the size of the single-node subtree.

Tree with only one node and it does not match the target color

How to Handle:

Return 0, indicating no valid subtree.

All nodes in the tree have the target color

How to Handle:

Return the total number of nodes in the tree.

No nodes in the tree have the target color

How to Handle:

Return 0, indicating no valid subtree.

Large tree to ensure the solution is scalable and does not cause stack overflow in recursive solutions

How to Handle:

Iterative approaches using stacks or queues can prevent stack overflow for very deep trees; consider using that approach.

Skewed tree (e.g., a linked list structure)

How to Handle:

Handle the skewed structure efficiently without unnecessary traversal of nonexistent branches.

Target color is negative or zero

How to Handle:

The solution must correctly handle any valid integer color value.