Maximize the Number of Target Nodes After Connecting Trees I

Maximize the Number of Target Nodes After Connecting Trees I

What is this problem about?

In this problem, you are given two separate undirected trees, edges1 and edges2, and an integer k. You are allowed to add exactly one edge to connect a node from Tree 1 to a node in Tree 2. Your goal is to maximize the number of "target nodes" in the newly combined tree. A node is a target node if its distance to a specific starting node in Tree 1 is less than or equal to k. You must return an array answering this for every possible starting node in Tree 1.

Why is this asked in interviews?

This problem is a fantastic test of Graph Traversal and Precomputation. Interviewers ask it because an unoptimized approach (trying every possible connection and running a full BFS for every node) results in $O(N^3)$ or worse. It forces candidates to realize that the two trees can be analyzed completely independently before the single connecting edge is simulated.

Algorithmic pattern used

This problem is solved using Independent BFS/DFS Precomputation.

1. Analyze Tree 2: Since we want to maximize nodes within distance k, we should connect Tree 1 to the node in Tree 2 that has the most nodes within distance k - 1 from it. We run a BFS from every node in Tree 2 to find this single optimal connection point and store its "max reach" value.
2. Analyze Tree 1: For every node i in Tree 1, we run a BFS to find how many nodes within Tree 1 are within distance k.
3. Combine: The total valid nodes for starting node i is simply (nodes in Tree 1 within distance k) + (optimal max reach from Tree 2 within distance k - 1).

Example explanation

Assume k = 2. Tree 2 has 3 nodes connected in a line: A - B - C.

• From A, distance 1 reaches B (1 node).
• From B, distance 1 reaches A and C (2 nodes). The optimal node to connect to in Tree 2 is B. Its max reach for k-1 (which is 1) is 2 nodes.

Tree 1 has 2 nodes: X - Y. For starting node X:

• Nodes in Tree 1 within distance 2: X and Y (2 nodes).
• We add the connecting edge from X to B.
• Nodes reached in Tree 2: B's reach is 2. Total for X = $2 + 2 = 4$. By precomputing Tree 2's best node, we answer Tree 1's queries in $O(1)$ time per node after the initial BFS passes.

Common mistakes candidates make

A frequent mistake is attempting to dynamically join the trees and run a full search. Since there are $N$ nodes in Tree 1 and $M$ nodes in Tree 2, simulating the connection for every pair $(i, j)$ takes $O(N \times M \times (N+M))$ time. The key insight is decoupling: the optimal entry point into Tree 2 is universally the same regardless of which node you start from in Tree 1.

Interview preparation tip

When an interview question allows you to "add one edge between two disconnected graphs", always look for independent properties. Precalculate the best attachment point for the "target" graph. Treat that attachment point as a static mathematical bonus (a flat integer) that you simply add to the local calculations of the "source" graph.