BFS - find nodes with k distance
Intuition\n From each node in tree1, we can visit all nodes with k distance. To connect with tree2, we have to connect an edge with takes a distance of 1. Hence
# Intuition\n* From each node in tree1, we can visit all nodes with k distance. To connect with tree2, we have to connect an edge with takes a distance of 1. Hence we can visit all nodes in tree2 within k-1 distance. \n* Where should we connect the edge? We can connect each node of tree1 with the node of tree2 from where we can visit max number of nodes within k-1 distance.\n\n# Approach\n* For each node u in the first tree, find the number of nodes at a distance of at most k from node u.\n\n* For each node v in the second tree, find the number of nodes at a distance of at most k - 1 from node v.\n\n# Complexity\n- Time complexity:\nTree1: To find nodes with k dist for each node = O(M^2)  \nTree2: To find nodes with k dist for each node = O(N^2) \nO(M^2 + N^2)\n\n- Space complexity:\nO(M^2 + N^2)\n\n![image.png](https://assets.leetcode.com/users/images/4d69a9de-81ad-43a2-a064-4724e7362b34_1733046801.2583191.png)\n\n# Code\n```python3 []\nclass Solution:\n    def maxTargetNodes(self, edges1: List[List[int]], edges2: List[List[int]], k: int) -> List[int]:\n        \n\n        def find(edges, k):\n\n            graph = defaultdict(list)\n\n            for i,j in edges:\n                graph[i].append(j)\n                graph[j].append(i)\n            \n            n = len(graph)\n\n            nodes_within_k_dist = [0] * n\n            if k<0: return nodes_within_k_dist\n\n            for src in range(n): \n                q = [[src,0]] \n                visited = set()\n                visited.add(src)\n                count = 1\n\n                while q:\n                    node,steps = q.pop(0)\n                    for nei in graph[node]:\n                        if nei not in visited and steps < k:\n                            count += 1\n                            q.append([nei,steps+1])\n                            visited.add(nei)\n            \n                nodes_within_k_dist[src] = count\n\n            return nodes_within_k_dist\n            \n        count1 = find(edges1,k)\n        count2 = find(edges2,k-1)\n        max_count2 = max(count2)\n\n        res = []\n        for count in count1:\n            res.append(count + max_count2) \n        \n        return res\n\n\n\n                \n        \n\n\n\n\n\n\n\n```
['Python3']