Maximum Subtree of the Same Color - Practice Coding Problems

Maximum Subtree of the Same Color - Problem

You are given a 2D integer array edges representing a tree with n nodes, numbered from 0 to n - 1, rooted at node 0, where edges[i] = [ui, vi] means there is an edge between the nodes vi and ui.

You are also given a 0-indexed integer array colors of size n, where colors[i] is the color assigned to node i.

We want to find a node v such that every node in the subtree of v has the same color. Return the size of such subtree with the maximum number of nodes possible.

Input & Output

Example 1 — Basic Tree

$ Input: edges = [[0,1],[1,2],[2,3],[3,4]], colors = [1,1,2,1,1]

› Output: 2

💡 Note: Node 1 has a subtree containing nodes {1, 4} both with color 1. This is the largest same-color subtree with size 2.

Example 2 — All Same Color

$ Input: edges = [[0,1],[0,2]], colors = [1,1,1]

› Output: 3

💡 Note: All nodes have color 1, so the entire tree starting from node 0 forms a same-color subtree of size 3.

Example 3 — No Large Subtrees

$ Input: edges = [[0,1],[0,2]], colors = [1,2,3]

› Output: 1

💡 Note: Each node has a different color, so the maximum same-color subtree size is 1 (any single node).

Constraints

2 ≤ edges.length ≤ 10⁵
0 ≤ edges[i][0], edges[i][1] < n
1 ≤ colors[i] ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input Tree

Tree with colored nodes represented by edges and colors arrays

Find Subtrees

Check each possible subtree for uniform color

Maximum Size

Return the size of largest same-color subtree

Key Takeaway

🎯 Key Insight: Use DFS to explore all possible subtrees and find the largest one with uniform node colors

Asked in

G Google 35 a Amazon 28 M Microsoft 22 f Meta 18

The key insight is to use DFS traversal to explore each possible subtree and check if all nodes have the same color. The optimal approach performs DFS from each node to find the largest uniform subtree. Best approach: DFS with subtree validation. Time: O(n²), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Check Every Node	O(n²)	O(n)	For each node, build its subtree and check if all nodes have the same color
Optimized DFS - Single Traversal	O(n²)	O(n)	Use single DFS traversal to find largest same-color subtree efficiently

Brute Force - Check Every Node — Algorithm Steps

Step 1: Build adjacency list representation of the tree
Step 2: For each node, perform DFS to check if entire subtree has same color
Step 3: Return the maximum subtree size found

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Tree

Create adjacency list from edges

Check Each Node

For each node, DFS to find same-color subtree size

Return Maximum

Track and return the largest subtree found

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_N 1000

int adj[MAX_N][MAX_N];
int adjSize[MAX_N];
int colors[MAX_N];
int n;

int dfs(int node, int parent, int targetColor) {
    if (colors[node] != targetColor) {
        return 0;
    }
    
    int size = 1;
    for (int i = 0; i < adjSize[node]; i++) {
        int neighbor = adj[node][i];
        if (neighbor != parent) {
            int childSize = dfs(neighbor, node, targetColor);
            if (childSize == 0) {
                return 0;
            }
            size += childSize;
        }
    }
    return size;
}

int solution(int edges[][2], int edgeCount, int* colorsInput, int colorCount) {
    n = colorCount;
    if (n == 1) return 1;
    
    // Initialize adjacency list
    for (int i = 0; i < n; i++) {
        adjSize[i] = 0;
        colors[i] = colorsInput[i];
    }
    
    // Build adjacency list
    for (int i = 0; i < edgeCount; i++) {
        int u = edges[i][0], v = edges[i][1];
        adj[u][adjSize[u]++] = v;
        adj[v][adjSize[v]++] = u;
    }
    
    int maxSize = 1;
    
    // Try each node as root of a same-color subtree
    for (int i = 0; i < n; i++) {
        int subtreeSize = dfs(i, -1, colors[i]);
        if (subtreeSize > maxSize) {
            maxSize = subtreeSize;
        }
    }
    
    return maxSize;
}

int main() {
    // Simplified input parsing for this format
    printf("%d\n", 1);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

For each of n nodes, we potentially traverse the entire subtree in worst case

⚠ Quadratic Growth

Space Complexity

O(n)

Adjacency list storage and recursion stack depth up to n

⚡ Linearithmic Space

23.4K Views

Medium Frequency

~25 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Check Every Node — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler