Java | DFS | With Detailed Explanation | Well Commented
Problem Description\n There exist two undirected trees with n and m nodes, with distinct labels in ranges [0, n - 1] and [0, m - 1], respectively.\n\n## You are
# Problem Description\n There exist two undirected trees with `n` and `m` nodes, with distinct labels in ranges `[0, n - 1]` and `[0, m - 1]`, respectively.\n\n## You are also provided:\n\n1. edges1 (a 2D integer array of size n - 1) which represents edges in the first tree, where `edges1[i] = [a_i, b_i]` indicates an edge between nodes a_i and b_i.\n2. edges2 (a 2D integer array of size m - 1) which represents edges in the second tree, where `edges2[i] = [u_i, v_i]` indicates an edge between nodes u_i and v_i.\n3. An integer k.\n\n## Target Node \nA node `u` is target to node `v` if the number of edges on the path from `u` to `v` is less than or equal to `k`. Note that a node is always target to itself.\n\n## Task\nReturn an array of size n, where the i-th value is the maximum possible number of nodes target to node i of the first tree if you connect one node from the first tree to another node in the second tree.\n\n# Intuition\nWe have to calculate maximum number of target nodes for all nodes of 1st tree, if we have to connect one node from the 1st tree to 2nd tree.\n\nLet we take the given example :- k = 2\n![{DDEBF5D4-0764-4BE6-AE16-9EC2B0047B61}.png](https://assets.leetcode.com/users/images/b276a8c1-ddbf-4452-b70f-af4de2316f6a_1733658742.8677986.png)\n\n1. Calculate the maximum number of target node for ech node of tree1 without connecting . That will be : \n    answer = {5,3,5,4,4}.\n\n    - From node 0 we can visit (0,1,2,3,4)\n    - From node 1 we can visit (0,1,2) and so on\n2. Now we have to attach one node from tree1 to tree2. For this we can follow this .\n \n    `ans[i] = tar nodes in T1 from i node + node with max tar nodes in T2 for k=k-1`\n\n3. For k = k-1 in Tree2 \n\n    - From node 0 = 4 i.e {0,1,2,3}\n    - From node 1 = 3 i.e {0,1,4}\n    - From node 2 = 4 i.e {0,2,7}\n    - From node 3 = 2 i.e {0,3}\n    - From node 4 = 4 i.e {1,4,5,6}\n    - So on.\n4. So in Tree 2 max is 4 . Now when we add it in answer we got resultant array.\n` answer = {9,7,9,8,8} `\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\nLooking From the constrains we can perform dfs for every node i.e.\n>     2 <= n, m <= 1000\n\n1. Build Graph from the given edges array\n2. Use DFS traversal to find max value of taget nodes that can be visited for each node in tree2 with k = k-1.\n3. Use again DFS to find maximum number of target node we can visit from a node in tree1 for each node and store in a result array.\n4. Adding max value in answer of each node of tree1 and return it.\n\n\n# Complexity\n- Time complexity: $$O(nk+mk)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n    Graphs : $$O(n+m)$$\n\n# Code\n```java []\nclass Solution {\n    public int[] maxTargetNodes(int[][] edges1, int[][] edges2, int k) {\n        int n = edges1.length;\n        int m = edges2.length;\n\n        // Pre calculation Array for both graphs\n        int[] arr1 = new int[n+1];\n        int[] arr2 = new int[m+1];\n\n        // Making graph from edges\n        HashMap<Integer,ArrayList<Integer>> g1 = new HashMap<>();\n        HashMap<Integer,ArrayList<Integer>> g2 = new HashMap<>();\n        \n        if(k==0){\n            Arrays.fill(arr1,1);\n            return arr1;\n        }\n\n        for(int[] i: edges1){\n            if(!g1.containsKey(i[0])) g1.put(i[0],new ArrayList<>());\n            if(!g1.containsKey(i[1])) g1.put(i[1],new ArrayList<>());\n            g1.get(i[0]).add(i[1]);\n            g1.get(i[1]).add(i[0]);\n        }\n\n        for(int[] i: edges2){\n            if(!g2.containsKey(i[0])) g2.put(i[0],new ArrayList<>());\n            if(!g2.containsKey(i[1])) g2.put(i[1],new ArrayList<>());\n            g2.get(i[0]).add(i[1]);\n            g2.get(i[1]).add(i[0]);\n        }\n        int max = 0;\n\n        for(int i=0;i<=m;i++){\n            max = Math.max(max,dfs(g2,k-1,i,new boolean[m+1]));\n        }\n        max++;\n        for(int i=0;i<=n;i++){\n            arr1[i] = dfs(g1,k,i,new boolean[n+1])+1+max;\n        }\n\n        return arr1;\n\n\n    }\n\n    public int dfs(HashMap<Integer,ArrayList<Integer>> g1, int k, int u,boolean[] vis){\n        if(k==0) return 0;\n        int min = 0;\n        vis[u] = true;\n        for(int i:g1.get(u)){\n            if(!vis[i]){\n                min += dfs(g1,k-1,i,vis)+1;\n            }\n        }\n        return min;\n    }\n    \n}\n```
['Tree', 'Depth-First Search', 'Breadth-First Search', 'Graph', 'Recursion', 'Java']