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:

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:

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:

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.