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 themaximum number of nodes possible.

Examples

Example 1:

1
2
3


Input: edges = [[0,1],[0,2],[0,3]], colors = [1,1,2,3]
Output: 1
Explanation: Each color is represented as: 1 -> Red, 2 -> Green, 3 -> Blue. We can see that the subtree rooted at node 0 has children with different colors. Any other subtree is of the same color and has a size of 1. Hence, we return 1.

Example 2:

1
2
3
4


Input: edges = [[0,1],[0,2],[0,3]], colors = [1,1,1,1]
Output: 4
Explanation: The whole tree has the same color, and the subtree rooted at node 0 has the most number of nodes which is 4. Hence, we return 4.
**![](https://fastly.jsdelivr.net/gh/doocs/leetcode@main/solution/3000-3099/3004.Maximum%20Subtree%20of%20the%20Same%20Color/images/20231216-134017.png)**

Example 3:

1
2
3


Input: edges = [[0,1],[0,2],[2,3],[2,4]], colors = [1,2,3,3,3]
Output: 3
Explanation: Each color is represented as: 1 -> Red, 2 -> Green, 3 -> Blue. We can see that the subtree rooted at node 0 has children with different colors. Any other subtree is of the same color, but the subtree rooted at node 2 has a size of 3 which is the maximum. Hence, we return 3.

Constraints:

n == edges.length + 1
1 <= n <= 5 * 10^4
edges[i] == [ui, vi]
0 <= ui, vi < n
colors.length == n
1 <= colors[i] <= 10^5
The input is generated such that the graph represented by edges is a tree.

Solution

Method 1 – DFS with Subtree Color Check

Intuition

To find the largest subtree where all nodes have the same color, we can use DFS to traverse the tree. For each node, we check if all nodes in its subtree share the same color. If so, we update the maximum size found.

Approach

Build the tree as an adjacency list from the edges.
Use DFS to traverse from the root (node 0).
For each node:
- Recursively check all children.
- If all children are valid and have the same color as the current node, the subtree is valid.
- Track the size of valid subtrees and update the maximum found.
Return the maximum size found.

Complexity

⏰ Time complexity: O(n) — Each node is visited once.
🧺 Space complexity: O(n) — For adjacency list and recursion stack.

C++

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


class Solution {
public:
    int maximumSubtreeSize(vector<vector<int>>& edges, vector<int>& colors) {
        int n = colors.size(), ans = 0;
        vector<vector<int>> g(n);
        for (auto& e : edges) {
            g[e[0]].push_back(e[1]);
            g[e[1]].push_back(e[0]);
        }
        function<pair<bool,int>(int,int)> dfs = [&](int u, int p) {
            int sz = 1;
            bool valid = true;
            for (int v : g[u]) {
                if (v == p) continue;
                auto [ok, sub_sz] = dfs(v, u);
                if (!ok || colors[v] != colors[u]) valid = false;
                sz += sub_sz;
            }
            if (valid) ans = max(ans, sz);
            return make_pair(valid, sz);
        };
        dfs(0, -1);
        return ans;
    }
};

Go

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


func maximumSubtreeSize(edges [][]int, colors []int) int {
    n := len(colors)
    g := make([][]int, n)
    for _, e := range edges {
        g[e[0]] = append(g[e[0]], e[1])
        g[e[1]] = append(g[e[1]], e[0])
    }
    ans := 0
    var dfs func(u, p int) (bool, int)
    dfs = func(u, p int) (bool, int) {
        sz := 1
        valid := true
        for _, v := range g[u] {
            if v == p { continue }
            ok, subSz := dfs(v, u)
            if !ok || colors[v] != colors[u] { valid = false }
            sz += subSz
        }
        if valid && sz > ans { ans = sz }
        return valid, sz
    }
    dfs(0, -1)
    return ans
}

Java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27


class Solution {
    public int maximumSubtreeSize(int[][] edges, int[] colors) {
        int n = colors.length, ans = 0;
        List<List<Integer>> g = new ArrayList<>();
        for (int i = 0; i < n; ++i) g.add(new ArrayList<>());
        for (int[] e : edges) {
            g.get(e[0]).add(e[1]);
            g.get(e[1]).add(e[0]);
        }
        class Helper {
            int dfs(int u, int p) {
                int sz = 1;
                boolean valid = true;
                for (int v : g.get(u)) {
                    if (v == p) continue;
                    int subSz = dfs(v, u);
                    if (colors[v] != colors[u]) valid = false;
                    sz += subSz;
                }
                if (valid) ans = Math.max(ans, sz);
                return valid ? sz : 0;
            }
        }
        new Helper().dfs(0, -1);
        return ans;
    }
}

Kotlin

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


class Solution {
    fun maximumSubtreeSize(edges: Array<IntArray>, colors: IntArray): Int {
        val n = colors.size
        val g = Array(n) { mutableListOf<Int>() }
        for (e in edges) {
            g[e[0]].add(e[1])
            g[e[1]].add(e[0])
        }
        var ans = 0
        fun dfs(u: Int, p: Int): Pair<Boolean, Int> {
            var sz = 1
            var valid = true
            for (v in g[u]) {
                if (v == p) continue
                val (ok, subSz) = dfs(v, u)
                if (!ok || colors[v] != colors[u]) valid = false
                sz += subSz
            }
            if (valid) ans = maxOf(ans, sz)
            return valid to sz
        }
        dfs(0, -1)
        return ans
    }
}

Python

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


def maximum_subtree_size(edges: list[list[int]], colors: list[int]) -> int:
    from collections import defaultdict
    n = len(colors)
    g: dict[int, list[int]] = defaultdict(list)
    for u, v in edges:
        g[u].append(v)
        g[v].append(u)
    ans = 0
    def dfs(u: int, p: int) -> tuple[bool, int]:
        sz = 1
        valid = True
        for v in g[u]:
            if v == p:
                continue
            ok, sub_sz = dfs(v, u)
            if not ok or colors[v] != colors[u]:
                valid = False
            sz += sub_sz
        if valid:
            nonlocal ans
            ans = max(ans, sz)
        return valid, sz
    dfs(0, -1)
    return ans

Rust

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


impl Solution {
    pub fn maximum_subtree_size(edges: Vec<Vec<i32>>, colors: Vec<i32>) -> i32 {
        use std::collections::HashMap;
        let n = colors.len();
        let mut g: HashMap<i32, Vec<i32>> = HashMap::new();
        for e in &edges {
            g.entry(e[0]).or_default().push(e[1]);
            g.entry(e[1]).or_default().push(e[0]);
        }
        let mut ans = 0;
        fn dfs(u: i32, p: i32, g: &HashMap<i32, Vec<i32>>, colors: &Vec<i32>, ans: &mut i32) -> (bool, i32) {
            let mut sz = 1;
            let mut valid = true;
            for &v in g.get(&u).unwrap_or(&vec![]) {
                if v == p { continue; }
                let (ok, sub_sz) = dfs(v, u, g, colors, ans);
                if !ok || colors[v as usize] != colors[u as usize] { valid = false; }
                sz += sub_sz;
            }
            if valid { *ans = (*ans).max(sz); }
            (valid, sz)
        }
        dfs(0, -1, &g, &colors, &mut ans);
        ans
    }
}

TypeScript

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


class Solution {
    maximumSubtreeSize(edges: number[][], colors: number[]): number {
        const n = colors.length;
        const g: number[][] = Array.from({length: n}, () => []);
        for (const [u, v] of edges) {
            g[u].push(v);
            g[v].push(u);
        }
        let ans = 0;
        function dfs(u: number, p: number): [boolean, number] {
            let sz = 1;
            let valid = true;
            for (const v of g[u]) {
                if (v === p) continue;
                const [ok, subSz] = dfs(v, u);
                if (!ok || colors[v] !== colors[u]) valid = false;
                sz += subSz;
            }
            if (valid) ans = Math.max(ans, sz);
            return [valid, sz];
        }
        dfs(0, -1);
        return ans;
    }
}

Problem#

Examples#

Solution#

Method 1 – DFS with Subtree Color Check#

Intuition#

Approach#

Complexity#

C++#

Go#

Java#

Kotlin#

Python#

Rust#

TypeScript#