LeetCode Problem 3372

Difficulty: 🟡 Medium
Topics: Tree, Depth-First Search, Breadth-First Search

Solution

LeetCode 3372 - Maximize the Number of Target Nodes After Connecting Trees I

Problem Understanding

We are given two separate undirected trees.

The first tree contains n nodes labeled from 0 to n - 1, and the second tree contains m nodes labeled from 0 to m - 1.

A node u is considered a target node for another node v if the shortest path distance between them is at most k.

For every node i in the first tree, we are allowed to add exactly one temporary edge connecting:

Problem Understanding

This problem gives us two separate undirected trees. The first tree has n nodes labeled from 0 to n - 1, and the second tree has m nodes labeled from 0 to m - 1.

For any two nodes, a node u is considered a target node of v if the shortest path distance between them is less than or equal to k. Since these are trees, there is exactly one simple path between any two nodes.

For every node i in the first tree, we are allowed to add exactly one edge connecting:

• one node from the first tree
• one node from the second tree

After adding this edge, we want to maximize how many nodes become target nodes of i.

Each query is independent. After computing the answer for one node i, the added edge is removed before processing the next node.

The important detail is that the new edge can connect any node from tree 1 to any node from tree 2. We are free to choose the best connection separately for every node i.

The output is an array answer where:

• answer[i] equals the maximum number of nodes within distance k from node i after optimally connecting the two trees.

Since both inputs are trees:

• there are no cycles
• there is exactly one simple path between every pair of nodes

The constraints are:

• n, m <= 1000
• k <= 1000

This is small enough that running BFS or DFS from every node is completely feasible.

Some important edge cases immediately stand out:

• k = 0, where only the node itself can be counted
• very small trees, such as trees with only 2 nodes
• highly unbalanced trees, like chains
• star-shaped trees where one node connects to all others
• cases where the second tree contributes nothing because traversing the bridge already consumes all allowed distance

The problem guarantees both graphs are valid trees, so we never need to handle disconnected components or invalid inputs. After adding this edge, we want to maximize the number of nodes that are within distance k from node i.

The important detail is that every query is independent. After computing the best answer for node i, the added edge is removed before processing the next node.

The result is an array where:

• answer[i] represents the maximum number of target nodes reachable from node i
• the count includes nodes from both trees after adding one connecting edge

The constraints are relatively small:

• n, m <= 1000
• both graphs are guaranteed to be valid trees
• k <= 1000

Because the graphs are trees and the total number of nodes is only around 2000, running BFS or DFS from every node is feasible.

There are several important observations and edge cases:

When k = 0, a node can only reach itself. Since crossing into the second tree requires using the newly added edge, no node in the second tree can be reached because that would require distance at least 1. Therefore every answer becomes 1.

Another important observation is that the newly added edge always consumes one distance unit. If we connect node a in the first tree to node b in the second tree, then any node in the second tree reachable from i must satisfy:

$$\text{dist}(i, a) + 1 + \text{dist}(b, x) \le k$$

This structure is the key to the optimized solution.

Because the input graphs are guaranteed to be trees:

• there are no cycles
• there is exactly one path between nodes
• BFS distance computation is straightforward and efficient

Approaches

Brute Force Approach

The brute force solution tries every possible way to connect the two trees.

For every node i in the first tree:

1. Try every node u in the first tree as the bridge endpoint.
2. Try every node v in the second tree as the bridge endpoint.
3. Add the temporary edge (u, v).
4. Run BFS from i in the combined graph.
5. Count how many nodes are within distance k.
6. Keep the maximum result.

This works because it explicitly evaluates every legal connection and directly computes the resulting reachable nodes. The brute force approach tries every possible connection between the two trees for every node in the first tree.

For a fixed node i in the first tree:

1. Try connecting every node a in the first tree with every node b in the second tree.
2. Build the temporary merged graph.
3. Run BFS from node i.
4. Count how many nodes are within distance k.
5. Keep the maximum count.

This approach is correct because it explicitly evaluates every valid way to connect the trees and computes the exact number of reachable nodes.

However, it is far too slow.

There are:

• n * m possible bridge choices per query
• n queries
• each BFS costs O(n + m)

The total complexity becomes roughly:

O(n * n * m * (n + m))

With n, m <= 1000, this becomes impractical.

Key Insight

The crucial observation is that the two trees contribute independently.

Suppose we want to compute the answer for node i.

If we connect:

• node u in tree 1
• node v in tree 2

then any node x in tree 2 is reachable from i with distance:

dist(i, u) + 1 + dist(v, x)

The bridge edge itself costs 1.

To maximize reachable nodes in tree 2, we should:

• spend as little distance as possible before entering tree 2

The best choice is always:

u = i

because then:

dist(i, u) = 0

Now the condition for nodes in tree 2 becomes:

1 + dist(v, x) <= k

which simplifies to:

dist(v, x) <= k - 1

Therefore:

• for tree 1, we only need the count of nodes within distance k from every node
• for tree 2, we only need the maximum count of nodes within distance k - 1 from any node

These can both be precomputed using BFS from every node.

• n * m possible edges to add
• each BFS costs O(n + m)
• and we repeat this for every node in the first tree

The total complexity becomes approximately:

$$O(n \times n \times m \times (n+m))$$

With n, m <= 1000, this becomes impractical.

Optimal Approach

The key insight is that the two trees can be analyzed independently.

Suppose we want the answer for node i in the first tree.

If we connect:

• node a in tree 1
• node b in tree 2

then any node x in tree 2 is reachable from i only if:

$$\text{dist}(i, a) + 1 + \text{dist}(b, x) \le k$$

To maximize reachable nodes in tree 2, we should minimize the cost spent inside tree 1.

The best choice is always:

$$a = i$$

because then:

$$\text{dist}(i, a) = 0$$

So we spend only one distance unit crossing the new edge.

That means:

• nodes reachable inside tree 1 are simply all nodes within distance k from i
• nodes reachable inside tree 2 are all nodes within distance k - 1 from the chosen connection node b

Therefore:

$$\text{answer}[i] = (\text{nodes within distance } k \text{ from } i \text{ in tree1}) + (\max \text{ nodes within distance } k-1 \text{ from any node in tree2})$$

This completely decouples the problem.

We can:

1. Precompute reachable counts for every node in tree 1 using BFS.
2. Precompute reachable counts for every node in tree 2 using BFS.
3. Find the maximum reachable count in tree 2 for distance k - 1.
4. Add that value to every node's count in tree 1.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n² × m × (n + m))	O(n + m)	Tries every possible bridge and recomputes BFS each time
Optimal	O(n² + m²)	O(n + m)	Precompute reachable counts with BFS from every node
Brute Force	O(n²m(n+m))	O(n+m)	Tries every possible connection and runs BFS each time
Optimal	O(n² + m²)	O(n+m)	Precomputes reachability counts independently for both trees

Algorithm Walkthrough

1. Build adjacency lists for both trees.

Since the graphs are trees and undirected, adjacency lists are the most efficient representation. They allow efficient BFS traversal from any node. 2. Create a helper BFS function.

The BFS function takes:

• an adjacency list
• a starting node
• a maximum allowed distance

It returns how many nodes are reachable within that distance. 3. Compute reachable counts for tree 1.

For every node i in tree 1:

• run BFS with limit k
• store how many nodes are within distance k

This value represents how many nodes inside tree 1 are always target nodes for i, regardless of where we connect the second tree. 4. Compute the best possible contribution from tree 2.

Any node reached in tree 2 must spend one edge crossing the bridge.

Therefore, nodes in tree 2 must satisfy:

distance <= k - 1

For every node in tree 2:

• run BFS with limit k - 1
• compute how many nodes are reachable
• keep the maximum value

5. Combine the results.

For every node i in tree 1:

answer[i] = reachable_in_tree1[i] + best_tree2

6. Return the final array.

Why it works

The key property is that crossing between trees always costs exactly one edge.

For any node i, the optimal bridge must connect directly from i into tree 2. Any other node in tree 1 would waste additional distance budget before even entering the second tree.

Once we connect directly from i to some node v in tree 2, the number of reachable nodes in tree 2 depends only on how many nodes are within distance k - 1 from v.

Thus the problem cleanly separates into:

• local reachability in tree 1
• best possible reachability in tree 2

This guarantees correctness. Since the input is given as edge lists, adjacency lists allow efficient BFS traversal. Trees are sparse graphs, so adjacency lists are the natural representation. 2. Create a helper BFS function.

The helper function takes:

• a graph
• a starting node
• a maximum allowed distance

It performs BFS and counts how many nodes are reachable within that distance. 3. Compute reachable counts for every node in tree 1.

For each node i:

• run BFS with limit k
• count all nodes within distance k
• store the result in count1[i]

4. Compute reachable counts for every node in tree 2.

Since crossing the connecting edge costs one step, only k - 1 distance remains for traversal inside tree 2.

For each node j in tree 2:

• run BFS with limit k - 1
• count reachable nodes
• track the maximum value across all nodes

5. Build the final answer.

For every node i in tree 1:

$$\text{answer}[i] = \text{count1}[i] + \text{bestTree2}$$

where bestTree2 is the maximum reachable count found in tree 2.

Why it works

The critical property is that the added edge contributes exactly one distance unit.

For node i, any path into tree 2 must look like:

$$i \rightarrow a \rightarrow b \rightarrow x$$

where:

• a is the connection node in tree 1
• b is the connection node in tree 2

The total distance becomes:

$$\text{dist}(i,a) + 1 + \text{dist}(b,x)$$

To maximize remaining distance budget for tree 2, we minimize dist(i,a). The minimum possible value is 0, achieved by choosing a = i.

Therefore the optimal strategy always connects node i directly to some node in tree 2.

Once that observation is made, the two trees become independent subproblems.

Python Solution

from collections import deque
from typing import List

class Solution:
    def maxTargetNodes(
        self,
        edges1: List[List[int]],
        edges2: List[List[int]],
        k: int
    ) -> List[int]:

        n = len(edges1) + 1
        m = len(edges2) + 1

        graph1 = [[] for _ in range(n)]
        graph2 = [[] for _ in range(m)]

        for u, v in edges1:
            graph1[u].append(v)
            graph1[v].append(u)

        for u, v in edges2:
            graph2[u].append(v)
            graph2[v].append(u)
        def build_graph(size: int, edges: List[List[int]]) -> List[List[int]]:
            graph = [[] for _ in range(size)]

            for u, v in edges:
                graph[u].append(v)
                graph[v].append(u)

            return graph

        graph1 = build_graph(n, edges1)
        graph2 = build_graph(m, edges2)

        def bfs_count(graph: List[List[int]], start: int, limit: int) -> int:
            if limit < 0:
                return 0

            visited = [False] * len(graph)
            queue = deque([(start, 0)])

            visited[start] = True
            count = 0

            while queue:
                node, dist = queue.popleft()

                if dist > limit:
                    continue

                count += 1

                for neighbor in graph[node]:
                    if not visited[neighbor]:
                        visited[neighbor] = True
                        queue.append((neighbor, dist + 1))

            return count

        tree1_counts = [0] * n

        for i in range(n):
            tree1_counts[i] = bfs_count(graph1, i, k)

        best_tree2 = 0

        for i in range(m):
            best_tree2 = max(
                best_tree2,
                bfs_count(graph2, i, k - 1)
        for node in range(n):
            tree1_counts[node] = bfs_count(graph1, node, k)

        best_tree2 = 0

        for node in range(m):
            best_tree2 = max(
                best_tree2,
                bfs_count(graph2, node, k - 1)
            )

        answer = []

        for count in tree1_counts:
            answer.append(count + best_tree2)

        return answer

The implementation starts by constructing adjacency lists for both trees. Since the input graphs are undirected, every edge is added in both directions.

The bfs_count helper performs a standard breadth-first search while tracking distances. It counts how many nodes are reachable within the allowed limit.

The special case limit < 0 is important because when k = 0, entering tree 2 is impossible. In that situation, tree 2 contributes zero nodes.

Next, the algorithm computes:

• reachable counts within distance k for every node in tree 1
• the maximum reachable count within distance k - 1 for tree 2

Finally, each result is formed by combining these two values. The implementation begins by converting both edge lists into adjacency lists. Since trees are undirected, every edge is inserted in both directions.

The bfs_count helper function computes how many nodes are reachable within a distance limit. BFS is ideal because it naturally explores nodes in increasing distance order.

The function keeps:

• a queue storing (node, distance)
• a visited array to avoid revisiting nodes
• a running count of valid nodes

For tree 1, BFS is run from every node using distance limit k.

For tree 2, BFS is run from every node using distance limit k - 1, because one edge is already consumed when crossing between trees.

The largest reachable count in tree 2 is stored in best_tree2.

Finally, each answer becomes:

$$\text{reachable in tree1} + \text{best reachable in tree2}$$

Go Solution

package main

import "container/list"

func maxTargetNodes(edges1 [][]int, edges2 [][]int, k int) []int {
	n := len(edges1) + 1
	m := len(edges2) + 1

	graph1 := make([][]int, n)
	graph2 := make([][]int, m)

	for _, edge := range edges1 {
		u, v := edge[0], edge[1]
		graph1[u] = append(graph1[u], v)
		graph1[v] = append(graph1[v], u)
	}

	for _, edge := range edges2 {
		u, v := edge[0], edge[1]
		graph2[u] = append(graph2[u], v)
		graph2[v] = append(graph2[v], u)
	}
	buildGraph := func(size int, edges [][]int) [][]int {
		graph := make([][]int, size)

		for _, edge := range edges {
			u, v := edge[0], edge[1]

			graph[u] = append(graph[u], v)
			graph[v] = append(graph[v], u)
		}

		return graph
	}

	graph1 := buildGraph(n, edges1)
	graph2 := buildGraph(m, edges2)

	bfsCount := func(graph [][]int, start int, limit int) int {
		if limit < 0 {
			return 0
		}

		visited := make([]bool, len(graph))

		type Pair struct {
		type State struct {
			node int
			dist int
		}

		queue := []Pair{{start, 0}}
		visited[start] = true

		count := 0
		head := 0

		for head < len(queue) {
			current := queue[head]
			head++

			node := current.node
			dist := current.dist

			if dist > limit {
		queue := list.New()
		queue.PushBack(State{start, 0})

		visited[start] = true

		count := 0

		for queue.Len() > 0 {
			front := queue.Front()
			queue.Remove(front)

			current := front.Value.(State)

			if current.dist > limit {
				continue
			}

			count++

			for _, neighbor := range graph[node] {
				if !visited[neighbor] {
					visited[neighbor] = true
					queue = append(queue, Pair{neighbor, dist + 1})
			for _, neighbor := range graph[current.node] {
				if !visited[neighbor] {
					visited[neighbor] = true
					queue.PushBack(State{
						node: neighbor,
						dist: current.dist + 1,
					})
				}
			}
		}

		return count
	}

	tree1Counts := make([]int, n)

	for i := 0; i < n; i++ {
		tree1Counts[i] = bfsCount(graph1, i, k)
	}

	bestTree2 := 0

	for i := 0; i < m; i++ {
		count := bfsCount(graph2, i, k-1)

		if count > bestTree2 {
			bestTree2 = count
		value := bfsCount(graph2, i, k-1)

		if value > bestTree2 {
			bestTree2 = value
		}
	}

	answer := make([]int, n)

	for i := 0; i < n; i++ {
		answer[i] = tree1Counts[i] + bestTree2
	}

	return answer
}

The Go version follows exactly the same algorithmic structure as the Python implementation.

A custom Pair struct stores (node, distance) values inside the BFS queue. Instead of using a deque, Go uses a slice with a moving head index for efficient queue operations.

Since all distances and counts are well within standard integer limits, regular int values are sufficient. The Go implementation follows the same logic as the Python version.

The main difference is that Go does not have a built in deque, so container/list is used to implement BFS queues.

Go slices naturally represent adjacency lists efficiently. Since all values fit comfortably within standard integer ranges, no overflow handling is required.

Unlike Python, Go requires explicit struct definitions for queue states, so a State struct stores (node, dist) pairs during BFS traversal.

Worked Examples

Example 1

edges1 = [[0,1],[0,2],[2,3],[2,4]]
edges2 = [[0,1],[0,2],[0,3],[2,7],[1,4],[4,5],[4,6]]
k = 2

Step 1: Compute Reachability in Tree 1

Tree 1 structure:

    1
    |
    0
    |
    2
   / \
  3   4

We run BFS from every node with distance limit 2.

Start Node	Reachable Nodes	Count
0	0,1,2,3,4	5
1	1,0,2	3
2	2,0,3,4,1	5
3	3,2,0,4	4
4	4,2,0,3	4

So:

tree1_counts = [5,3,5,4,4]

Step 2: Compute Best Reachability in Tree 2

Since crossing the bridge costs one edge:

remaining distance = k - 1 = 1

We compute nodes reachable within distance 1.

Start Node	Reachable Count
0	4
1	3
2	3
3	2
4	4
5	2
6	2
7	2

Best contribution:

best_tree2 = 4

Step 3: Build Final Answer

Node	Tree 1 Count	Best Tree 2	Final
0	5	4	9
1	3	4	7
2	5	4	9
3	4	4	8
4	4	4	8

Final answer:

[9,7,9,8,8]

Example 2

edges1 = [[0,1],[0,2],[0,3],[0,4]]
edges2 = [[0,1],[1,2],[2,3]]
k = 1

Tree 1 Reachability

Distance limit is 1.

Start Node	Reachable Count
0	5
1	2
2	2
3	2
4	2

Tree 2 Reachability

Remaining distance:

k - 1 = 0

Only the connected node itself is reachable.

Start Node	Reachable Count
0	1
1	1
2	1
3	1

So:

best_tree2 = 1

Final Computation

Node	Tree 1	Tree 2	Final
0	5	1	6
1	2	1	3
2	2	1	3
3	2	1	3
4	2	1	3

Final answer:

[6,3,3,3,3]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n² + m²)	BFS is run from every node in both trees
Space	O(n + m)	Adjacency lists, visited arrays, and BFS queue

Each BFS on a tree visits every node once, giving O(V) complexity per traversal.

Since we run BFS:

• n times on the first tree
• m times on the second tree

the total complexity becomes:

O(n² + m²)

With n, m <= 1000, this is efficient enough.

Test Cases

from typing import List

class Solution:
    def maxTargetNodes(self, edges1: List[List[int]], edges2: List[List[int]], k: int) -> List[int]:
        from collections import deque

        n = len(edges1) + 1
        m = len(edges2) + 1

        graph1 = [[] for _ in range(n)]
        graph2 = [[] for _ in range(m)]

        for u, v in edges1:
            graph1[u].append(v)
            graph1[v].append(u)

        for u, v in edges2:
            graph2[u].append(v)
            graph2[v].append(u)

        def bfs(graph, start, limit):
            if limit < 0:
                return 0

            visited = [False] * len(graph)
            visited[start] = True

            queue = deque([(start, 0)])
            count = 0

            while queue:
                node, dist = queue.popleft()

                if dist > limit:
                    continue

                count += 1

                for nei in graph[node]:
                    if not visited[nei]:
                        visited[nei] = True
                        queue.append((nei, dist + 1))

            return count

        first = [bfs(graph1, i, k) for i in range(n)]
        best = max(bfs(graph2, i, k - 1) for i in range(m))

        return [x + best for x in first]

sol = Solution()

# Example 1
assert sol.maxTargetNodes(
    [[0,1],[0,2],[2,3],[2,4]],
    [[0,1],[0,2],[0,3],[2,7],[1,4],[4,5],[4,6]],
    2
) == [9,7,9,8,8]

# Example 2
assert sol.maxTargetNodes(
    [[0,1],[0,2],[0,3],[0,4]],
    [[0,1],[1,2],[2,3]],
    1
) == [6,3,3,3,3]

# k = 0, cannot reach second tree
assert sol.maxTargetNodes(
    [[0,1]],
    [[0,1]],
    0
) == [1,1]

# Smallest valid trees
assert sol.maxTargetNodes(
    [[0,1]],
    [[0,1]],
    1
) == [3,3]

# Chain trees
assert sol.maxTargetNodes(
    [[0,1],[1,2],[2,3]],
    [[0,1],[1,2]],
    2
) == [5,6,6,5]

# Star-shaped tree
assert sol.maxTargetNodes(
    [[0,1],[0,2],[0,3]],
    [[0,1],[0,2],[0,3]],
    1
) == [5,3,3,3]

# Large k reaching entire trees
assert sol.maxTargetNodes(
    [[0,1],[1,2]],
    [[0,1],[1,2],[2,3]],
    10
) == [7,7,7]

print("All tests passed!")

Test Summary

Test	Why
Example 1	Validates general mixed tree structure
Example 2	Tests star tree and small distance
k = 0	Ensures second tree contributes nothing
Smallest valid trees	Verifies minimum constraints
Chain trees	Tests deep linear traversal
Star-shaped tree	Tests highly connected center
Large k	Ensures full-tree reachability

Edge Cases

Case 1: k = 0

When k = 0, a node can only reach itself.

This is tricky because entering the second tree requires crossing one edge, which already exceeds the allowed distance.

A buggy implementation might accidentally count one node from the second tree anyway.

The implementation handles this cleanly because BFS immediately returns 0 whenever the limit becomes negative:

if limit < 0:
    return 0

So the second tree contributes nothing.

Case 2: Extremely Unbalanced Trees

A chain-shaped tree can create large distances between nodes.

For example:

0 - 1 - 2 - 3 - 4

Some naive implementations incorrectly assume balanced traversal depth or use recursive DFS that risks recursion depth issues.

This solution uses iterative BFS, which safely handles all tree shapes.

Case 3: Large k

If k exceeds the diameter of the tree, every node becomes reachable.

A buggy implementation might continue unnecessary traversal logic or incorrectly prune nodes.

Since BFS only checks:

if dist > limit:
    continue

all nodes are naturally counted once the distance limit is large enough.

Case 4: Optimal Bridge Placement

A common mistake is trying all bridge endpoints in tree 1.

The key observation is that connecting directly from node i is always optimal because every extra step inside tree 1 wastes distance budget.

The implementation encodes this insight mathematically by independently computing:

• nodes reachable within k in tree 1
• nodes reachable within k - 1 in tree 2

This guarantees the optimal bridge choice is always considered implicitly. k =