Maximum Subtree of the Same Color in Java
A tree with n nodes is represented as a 2D integer array of edges, numbered from 0 to n + 1, and rooted at node 0. The notation edges[i] = [ui, vi] indicates that there is an edge between nodes vi and ui. Additionally, a 0-indexed integer array of colors of size n has been given to us, with colors [i] denoting the color that corresponds to node i.
Our task is to find a node v such that each node in v's subtree has the same colour. Then, return the size of the largest feasible subtree with this many nodes.
Example 1:
Input:
![Maximum Subtree of the Same Color in Java](https://static.tutorialandexample.com/java/maximum-subtree-of-the-same-color-in-java1.png)
int edges = [[0,1],[0,2],[0,3]] int colors = [1,1,1,1]
Output:
The maximum subtree size is 4
Explanation:
The whole tree is the same color, and the subtree with its root at node 0 has the greatest number of nodes—four. As a result, we return 4.
Example 2:
Input:
![Maximum Subtree of the Same Color in Java](https://static.tutorialandexample.com/java/maximum-subtree-of-the-same-color-in-java2.png)
int edges = [[0,1],[0,2],[0,3]] int colors = [1,1,2,3]
Output:
The maximum subtree size is 1
Explanation:
The representation of each color is as follows: 1 -> Red, 2 -> Green, and 3 -> Blue. The children of the subtree rooted at node 0 have various colors. Every other subtree has a size of 1 and is the same color. As a result, we return 1.
Example 3:
Input:
![Maximum Subtree of the Same Color in Java](https://static.tutorialandexample.com/java/maximum-subtree-of-the-same-color-in-java3.png)
int edges = [[0,1],[0,2],[2,3],[2,4]] int colors = [1,2,3,3,3]
Output:
The maximum subtree size is 3
Explanation:
The representation of each color is as follows: 1 -> Red, 2 -> Green, and 3 -> Blue. The children of the subtree rooted at node 0 have various colors. The color of all other subtrees is the same; however, the maximum size of the subtree rooted at node 2 is 3. As a result, we return 3.
Approach: Using DFS (Depth First Search)
To create an adjacency list adj, where adj[a] represents all of the node a's neighboring nodes, we first build one using the data on edges provided in the problem and indicate all nodes next to a node of length n; the number of nodes in the subtree with node an as the root is represented by size [a].
Next, we create a function called dfs(a, fa) that will determine if the subtree that has a node and as its root satisfies the problem's conditions. The following is the procedure used to execute the function dfs(a, fa).
Algorithm:
Step 1: To determine whether the subtree with the node as the root satisfies the problem's needs, we first initialize a variable called temp, which is initially true.
Step 2: Next, we go over each of the nodes a's neighboring nodes, b.
Step 2.1: We recursively call dfs(b, a), store the return value in the variable v, update temp to the value of temp, and then colors[a] = colors[b] ^ temp, where ^ stands for the logical AND operation if b is not the parent node fa of a.
Step 2.2: Next, we should update the to size [a] = size [a] + size [b].
Step 3: We proceed to evaluate the temp value. We update the answer with res = max(res, size[a]) if temp is true.
Step 4: We finally return the value of temp.
Step 5: We call to this as dfs(0, -1), where 0 indicates the number of the root node, and -1 indicates the non-existence of a parent node for the root node. The final result is RES.
Implementation:
FileName: MaxSubtreeColors.java
import java.io.*; import java.util.*; public class MaxSubtreeColors { private List[] adj; private int[] color; private int[] size; private int res; // Method for finding the maximum subtree size public int maximumSubtree (int[][] e, int[] color) { int n = e.length + 1; adj = new List[n]; size = new int[n]; this.color = color; Arrays.fill(size, 1); Arrays.setAll(adj, i -> new ArrayList<>()); // creating the adjacency list for (var edge : e) { int a = edge[0], b = edge[1]; adj[a].add(b); adj[b].add(a); } //Implementing the depth-first search for //Finding the maximum subtree size dfs(0, -1); return res; } private boolean dfs(int a, int fa) { boolean temp= true; // iterate for the children node a of the tree for (int b : adj[a]) { // omit the revisiting of the parent node if (b != fa) { // recursive call of the dfs // for the children node 'b' denoting // its parent node as 'a' boolean v = dfs(b, a); // check if the colors of both 'a' and 'b' are equal // subtree, which is rooted at 'b' is equal temp = temp && color [a] == color[b] && v; size[a] += size[b]; } } // if subtree obtained at 'a' is valid //Update the maximum subtree size. if (temp) { res = Math.max(res, size[a]); } return temp; } public static void main(String[] args) { MaxSubtreeColors obj = new MaxSubtreeColors(); int[][] e = {{0, 1}, {0, 2}, {2, 3}, {2, 4}}; int[] color = {1, 2, 3, 3, 3}; int maxSize = obj.maximumSubtree(e, color); System.out.println("The maximum subtree size is " + maxSize); } }
Output:
The maximum subtree size is 3
Complexity Analysis:
The time complexity is O(N), and the space complexity is O(N), where N represents the number of Nodes present in the tree.