#3372

Medium

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

Maximize the Number of Target Nodes After Connecting Trees I

Maximize the number of target nodes after connecting two trees using binary tree traversal and state tracking.

tree depth first search breadth first search

Problem Statement

Given two undirected trees, each with n and m nodes, the task is to maximize the number of target nodes after connecting nodes from the first tree to the second tree. You are provided two 2D arrays edges1 and edges2 describing the edges of the two trees and an integer k. A node u is considered a target to node v if the path from u to v has a length of at most k edges.

For each node u in the first tree, you need to find the number of nodes in the second tree that are reachable within k edges. Then, find the maximum number of reachable nodes by connecting each node from the first tree to any node from the second tree. The goal is to calculate this maximum for each node in the first tree.

Examples

Example 1

Input: 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

Output: [9,7,9,8,8]

Example 2

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

Output: [6,3,3,3,3]

For every i , connect node i of the first tree with any node of the second tree.

Constraints

2 <= n, m <= 1000
edges1.length == n - 1
edges2.length == m - 1
edges1[i].length == edges2[i].length == 2
edges1[i] = [ai, bi]
0 <= ai, bi < n
edges2[i] = [ui, vi]
0 <= ui, vi < m
The input is generated such that edges1 and edges2 represent valid trees.
0 <= k <= 1000

Solution Approach

Binary Tree Traversal

Use depth-first search (DFS) or breadth-first search (BFS) to traverse both trees. For each node in the first tree, calculate how many nodes in the second tree are within k edges using a simple traversal.

State Tracking with BFS/DFS

Track the state of each node while traversing the trees. Maintain an array or counter to keep track of reachable nodes within the given distance k. This allows for efficient counting of nodes without redundant calculations.

Maximizing Reachable Nodes

For each node in the first tree, connect it to every possible node in the second tree. For each connection, calculate the number of nodes that are reachable from that connection and find the maximum.

Complexity Analysis

Metric	Value
Time	O(n^2 + m^2)
Space	O(n + m)

The time complexity is O(n^2 + m^2), as each node from the first tree is connected to each node from the second tree, and a traversal (DFS/BFS) is performed for each connection. The space complexity is O(n + m), which accounts for the storage of nodes and their respective states in both trees.

What Interviewers Usually Probe

Ability to efficiently implement DFS/BFS for tree traversal
Skill in tracking and updating node states during traversal
Understanding of tree connection and maximum reachable node calculations

Common Pitfalls or Variants

Common pitfalls

Inefficient traversal leading to excessive recomputation of reachable nodes
Forgetting to update reachable node counts correctly during the traversal
Overlooking edge cases such as disconnected nodes or multiple valid connections

Follow-up variants

Consider trees of different sizes, which may affect the time complexity of the solution.
Modify the problem to connect nodes based on different distance constraints.
Extend the problem to include multiple trees and their connections.

FAQ

What is the key technique used to solve the problem?

The key technique is binary-tree traversal with depth-first search (DFS) or breadth-first search (BFS) combined with state tracking to calculate reachable nodes within a given distance k.

How do I connect nodes from two trees efficiently?

You can connect nodes from the first tree to any node in the second tree, and for each connection, calculate the number of reachable nodes within k edges.

What pattern does this problem follow?

This problem follows the binary-tree traversal and state tracking pattern, which is often used to count reachable nodes or calculate distances between nodes in tree-based problems.

What is the time complexity of the solution?

The time complexity of the solution is O(n^2 + m^2), where n is the number of nodes in the first tree and m is the number of nodes in the second tree.

What is the role of the integer `k` in the problem?

The integer k determines the maximum distance (in terms of the number of edges) between two nodes for one to be considered a target node of the other.

terminal

Solution

Solution 1: Enumeration + DFS

According to the problem description, to maximize the number of target nodes for node $i$, we must connect node $i$ to one of the nodes $j$ in the second tree. Therefore, the number of target nodes for node $i$ can be divided into two parts:

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

class Solution:
    def maxTargetNodes(
        self, edges1: List[List[int]], edges2: List[List[int]], k: int
    ) -> List[int]:
        def build(edges: List[List[int]]) -> List[List[int]]:
            n = len(edges) + 1
            g = [[] for _ in range(n)]
            for a, b in edges:
                g[a].append(b)
                g[b].append(a)
            return g

        def dfs(g: List[List[int]], a: int, fa: int, d: int) -> int:
            if d < 0:
                return 0
            cnt = 1
            for b in g[a]:
                if b != fa:
                    cnt += dfs(g, b, a, d - 1)
            return cnt

        g2 = build(edges2)
        m = len(edges2) + 1
        t = max(dfs(g2, i, -1, k - 1) for i in range(m))
        g1 = build(edges1)
        n = len(edges1) + 1
        return [dfs(g1, i, -1, k) + t for i in range(n)]

Continue Practicing

#3373 maximize the number of target nodes after connecting trees ii #3203 find minimum diameter after merging two trees #2641 cousins in binary tree ii