LeetCode 2277 - Closest Node to Path in Tree

The problem is asking us to process queries on a tree structure. Each query gives a path between two nodes starti and endi and a third node nodei.

leetcodehardarraytreedepth-first-searchbreadth-first-search

LeetCode Problem 2277

Difficulty: 🔴 Hard
Topics: Array, Tree, Depth-First Search, Breadth-First Search

Solution

Problem Understanding

The problem is asking us to process queries on a tree structure. Each query gives a path between two nodes starti and endi and a third node nodei. We are asked to find which node along the path is closest to nodei in terms of the number of edges separating them, also known as the distance in a tree.

The tree is represented as n nodes labeled from 0 to n - 1 and an edges list that connects the nodes bidirectionally. The key constraint is that the graph is guaranteed to be a tree, meaning it is connected and contains no cycles. The number of nodes and queries is relatively small (n <= 1000 and query.length <= 1000), so solutions with cubic complexity may be acceptable, but we can optimize further using tree properties.

Edge cases to consider include queries where starti equals endi (the path is a single node), the node nodei itself is on the path, and trees that are highly unbalanced (like a chain).

Approaches

Brute Force

The brute-force approach is straightforward. For each query, first find the path from starti to endi. This can be done using BFS or DFS to traverse the tree and record the parent of each node. Then, for each node on the path, compute the distance to nodei using another BFS from nodei. Return the node with the minimum distance.

While this works, it is inefficient because for each query, we might perform a BFS on the entire tree multiple times. For m queries and n nodes, the time complexity is roughly O(m * n) per BFS, giving O(m * n^2) overall, which may be slow for the upper bounds (1000 * 1000^2 = 10^9 operations).

Optimal Approach

The key observation is that in a tree, distance between nodes can be computed efficiently if we precompute distances from every node using BFS, or more elegantly, using Lowest Common Ancestor (LCA) techniques combined with a parent map to reconstruct paths.

  1. Precompute the distance between every node using BFS from each node. This gives a distance[node1][node2] table.
  2. For each query, generate the path from starti to endi using the parent map from BFS.
  3. For each node on that path, look up its distance to nodei from the precomputed table.
  4. Return the node with the minimum distance.

This reduces repeated BFS calls for every query and ensures quick lookup of distances.

Approach Time Complexity Space Complexity Notes
Brute Force O(m * n^2) O(n) BFS per query per path node
Optimal O(n^2 + m * n) O(n^2) Precompute all-pairs distances; path extraction via parent map

Algorithm Walkthrough

  1. Construct an adjacency list graph from the given edges for easy traversal.

  2. Precompute distances between all pairs of nodes using BFS from each node. Store this in a 2D list distances[n][n].

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

  4. Perform BFS or DFS from start to end to reconstruct the path between them. Track the parent of each node to backtrack the path.

  5. Initialize closest_node and min_distance variables.

  6. Iterate through each node on the path and check distances[node_on_path][node].

  7. If this distance is smaller than min_distance, update closest_node.

  8. After traversing the path, append closest_node to the answer.

  9. Return the answer list after processing all queries.

Why it works: The precomputed distances table ensures that we can check the distance from any node to any other in O(1) time. The path reconstruction guarantees we only consider nodes on the valid path between start and end. This satisfies the query requirements.

Python Solution

from collections import deque
from typing import List

class Solution:
    def closestNode(self, n: int, edges: List[List[int]], query: List[List[int]]) -> List[int]:
        graph = [[] for _ in range(n)]
        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)
        
        # Precompute all-pairs distances
        distances = [[0]*n for _ in range(n)]
        
        def bfs(start: int):
            dist = [-1] * n
            dist[start] = 0
            q = deque([start])
            while q:
                node = q.popleft()
                for nei in graph[node]:
                    if dist[nei] == -1:
                        dist[nei] = dist[node] + 1
                        q.append(nei)
            return dist
        
        for i in range(n):
            distances[i] = bfs(i)
        
        res = []
        for start, end, node in query:
            # Reconstruct path from start to end using BFS parent map
            parent = [-1] * n
            q = deque([start])
            visited = [False] * n
            visited[start] = True
            while q:
                curr = q.popleft()
                if curr == end:
                    break
                for nei in graph[curr]:
                    if not visited[nei]:
                        visited[nei] = True
                        parent[nei] = curr
                        q.append(nei)
            
            # Build the path
            path = []
            curr = end
            while curr != -1:
                path.append(curr)
                curr = parent[curr]
            path.reverse()
            
            # Find closest node on path to the target node
            min_dist = float('inf')
            closest_node = -1
            for p in path:
                if distances[p][node] < min_dist:
                    min_dist = distances[p][node]
                    closest_node = p
            res.append(closest_node)
        
        return res

Implementation Notes: The BFS precomputes distances between all node pairs efficiently for small trees. The parent map allows path reconstruction without DFS recursion. Each query then becomes a simple scan over the path nodes using O(1) distance lookups.

Go Solution

package main

func closestNode(n int, edges [][]int, query [][]int) []int {
    graph := make([][]int, n)
    for _, e := range edges {
        u, v := e[0], e[1]
        graph[u] = append(graph[u], v)
        graph[v] = append(graph[v], u)
    }

    // Precompute distances using BFS
    distances := make([][]int, n)
    for i := range distances {
        distances[i] = make([]int, n)
        for j := range distances[i] {
            distances[i][j] = -1
        }
        q := []int{i}
        distances[i][i] = 0
        for len(q) > 0 {
            node := q[0]
            q = q[1:]
            for _, nei := range graph[node] {
                if distances[i][nei] == -1 {
                    distances[i][nei] = distances[i][node] + 1
                    q = append(q, nei)
                }
            }
        }
    }

    res := []int{}
    for _, qu := range query {
        start, end, node := qu[0], qu[1], qu[2]

        parent := make([]int, n)
        for i := range parent {
            parent[i] = -1
        }
        visited := make([]bool, n)
        q := []int{start}
        visited[start] = true
        for len(q) > 0 {
            curr := q[0]
            q = q[1:]
            if curr == end {
                break
            }
            for _, nei := range graph[curr] {
                if !visited[nei] {
                    visited[nei] = true
                    parent[nei] = curr
                    q = append(q, nei)
                }
            }
        }

        path := []int{}
        for curr := end; curr != -1; curr = parent[curr] {
            path = append([]int{curr}, path...)
        }

        minDist := n + 1
        closest := -1
        for _, p := range path {
            if distances[p][node] < minDist {
                minDist = distances[p][node]
                closest = p
            }
        }
        res = append(res, closest)
    }

    return res
}

Go Implementation Notes: The BFS uses slices as queues. Precomputed distances are handled similarly. Slice prepending is used to reverse the path efficiently. Care is taken to initialize the distance matrix with -1.

Worked Examples

Example 1

Input: n = 7, edges = [[0,1],[0,2],[0,3],[1,4],[2,5],[2,6]], query = [[5,3,4],[5,3,6]]

Step 1: BFS distances precomputed.

Step 2: For query [5,3,4]:

  • Path from 5 to 3: [5,2,0,3]
  • Distance to node 4: [2,3,2,3] → closest node = `0