Maximize the Number of Target Nodes After Connecting Trees I - Solution & Explanation

Problem Overview: You are given two separate trees. You may connect exactly one node from the first tree to one node from the second tree with a new edge. For every node in the first tree, compute the maximum number of target nodes reachable within distance k after the connection is made. The goal is to choose the best node in the second tree so the reachable node count is maximized.

Approach 1: Breadth-First Search (BFS) Traversal (O(n^2 + m^2) time, O(n + m) space)

Treat both trees independently first. For each node in tree1, run a BFS to count how many nodes are within distance k. This produces an array where count1[i] represents reachable nodes if traversal stays inside tree1. Next, evaluate tree2 separately. Because one connecting edge consumes one step, nodes in tree2 must be within distance k-1 from the chosen connection node. Run BFS from every node in tree2 and compute how many nodes fall within distance k-1, then keep the maximum value. That maximum can be paired with any node in tree1 because you can always connect to the best node in tree2. The final answer for each node i becomes count1[i] + bestTree2. This approach works well because BFS naturally explores nodes level by level and stops once distance exceeds k. Tree traversal details rely on standard Breadth-First Search techniques.

Approach 2: Depth-First Search (DFS) with Memoization (O(n^2 + m^2) time, O(n + m) space)

The same distance counting can be implemented using recursive DFS. From each starting node, perform a depth-limited DFS that stops once the remaining distance becomes negative. Memoization can cache partial results for (node, remainingDistance) to avoid recomputing overlapping subtrees. This is useful when multiple DFS traversals revisit the same subtree with the same remaining distance. The logic mirrors the BFS approach: compute reachable counts within distance k for nodes in tree1 and within k-1 for nodes in tree2, then combine them using the maximum value from tree2. DFS implementations rely on adjacency lists and recursive traversal patterns from Depth-First Search on a tree.

Recommended for interviews: The BFS approach is usually expected. It is straightforward, avoids recursion depth issues, and clearly models the distance constraint. Showing the brute-force BFS from every node demonstrates understanding of tree traversal, while recognizing that the second tree only needs the global maximum shows the optimization insight interviewers look for.