Solution: Closest Node to Path in Tree

Statement

You are given a positive integer, n, representing the number of nodes in a tree, numbered from $0$ to $n-1$. You are also given a 2D integer array edges of length $n-1$, where edges[i] $= [u_i, v_i]$ indicates that there is a bidirectional edge connecting nodes $u_i$ and $v_i$.

You are also given a 2D integer array query of length $m$, where query[i] $= [start_i, end_i, node_i]$.

For each query i, find the node on the path between $start_i$ and $end_i$ that is closest to $node_i$ in terms of the number of edges.

Return an integer array where the value at index $i$ corresponds to the answer for the $i^{th}$ query.

Note: If there are multiple such nodes at the same minimum distance, return the one with the smallest index.

Constraints:

• $1 \leq$ n $\leq 1000$

• edges.length $== n - 1$

• edges[i].length $== 2$

• $0 \leq u_i, v_i \leq n-1$

• $u_i \space != v_i$

• $1 \leq$ query.length $\leq 1000$

• query[i].length $== 3$

• $0 \leq start_i, end_i, node_i \leq n-1$

• The graph is a tree.

Solution

The solution’s essence lies in first determining the exact path between two nodes in a tree using breadth-first search (BFS), and then identifying which node along that path is closest to a third given node. To do this, we perform a second BFS from the third node to compute the shortest distance to all other nodes in the tree. Finally, by comparing these distances for each node on the path, we select the one with the minimum distance, breaking ties by choosing the smaller node index.

Using the intuition above, we implement the algorithm as follows:

1. Initialize a 2D array, tree, to store the given tree as an adjacency list to represent node connections.

2. For each edge [u, v] in edges, add v to tree[u] and u to tree[v]. This builds a bidirectional structure from the input edges.

3. Initialize an array, answer, to store the answer to each query.

4. For each query [start, end, node]:

   1. Use BFS to find the path from start to end:

      1. Initialize an array, parents, of size n with all entries as -1 to keep track of each node’s parent.

      2. Create a queue and a visited array to perform standard BFS.

      3. Push start into the queue and mark it as visited.

      4. For every dequeued node:

         1. If it equals end, break the loop.

         2. Otherwise, enqueue all unvisited neighbors, mark them visited in the visited array, and record their parent in the parents array.

   2. Reconstruct the path from start to end:

      1. Starting from end, backtrack using the parents array until reaching start.

      2. Collect all nodes along this path into a path array.

      3. Reverse the path to get the correct order from start to end.

   3. Use BFS again to calculate the shortest distance from the node to all other nodes:

      1. Initialize a dist array of size n, all set to the maximum integer value.

      2. Set dist[node] = 0 and start BFS from node.

      3. For each dequeued node:

         1. For all its unvisited neighbors (i.e., dist[v] is still at maximum integer value), set dist[v] = dist[u] + 1 and enqueue them.

   4. Identify the closest node on the path to node:

      1. Initialize minDist with the maximum integer value and answerNode with -1.

      2. Traverse each node p in the path:

         1. If dist[p] is less than minDist, or if the distance is equal and p is smaller than answerNode, update both minDist and answerNode.

      3. Add answerNode to the answer array.

5. After processing all queries, return the answer array containing the closest node on each path.

Let’s look at the following illustration to get a better understanding of the solution: