We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Closest Node to Path in Tree

Number: 2420

Difficulty: Hard

Paid? Yes

Companies: N/A

Problem Description

Given a tree with n nodes (numbered 0 to n-1) and an edge list representing its structure, you are provided with several queries. Each query consists of three integers: start, end, and target. For each query, you need to determine the node along the unique path from start to end that is closest (in terms of shortest path distance in the tree) to the target node.

Key Insights

  • The tree structure guarantees a unique simple path between any two nodes.
  • The first challenge is to extract the path from start to end; this can be done using a DFS or BFS since the tree is undirected.
  • Once the path is determined, we must find the node from this path that minimizes the distance to the query target node.
  • For finding distances in the tree (which is unweighted), a BFS starting from the target node provides the shortest distances to all nodes.
  • Given the constraints (n, number of queries ≤ 1000), a solution that performs DFS to find the path and BFS for each query is efficient enough.

Space and Time Complexity

Time Complexity: O(m * n) where m is the number of queries and n is the number of nodes. Each query may require a DFS (to find the path) and a BFS (to compute distances from the target) over the tree. Space Complexity: O(n) to store the graph and additional O(n) for recursion/BFS queues per query.

Solution

We first build an adjacency list for the tree from the given edges. For each query, we follow these steps:

  1. Use DFS to find and record the unique path from the start node to the end node.
  2. Use BFS starting from the target node to calculate the shortest distance from the target to every other node in the tree.
  3. Iterate over the nodes in the obtained path and select the node having the minimum distance to the target.
  4. Return the selected node as the answer for that query.

This approach leverages both DFS and BFS techniques and takes advantage of the tree’s properties (unique paths) to solve the problem directly.

Code Solutions

# Python Implementation

from collections import defaultdict, deque

def closestNode(n, edges, queries):
    # Build the graph's adjacency list representation
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
    
    def find_path(start, end):
        # DFS to find path from start to end.
        stack = [(start, [start])]
        visited = set()
        while stack:
            node, path = stack.pop()
            if node == end:
                return path
            if node in visited:
                continue
            visited.add(node)
            for neighbor in graph[node]:
                if neighbor not in visited:
                    stack.append((neighbor, path + [neighbor]))
        return []  # Although in a tree, path always exists.
    
    def bfs_from_target(target):
        # BFS to compute shortest distances from target node.
        distances = [-1] * n
        queue = deque([target])
        distances[target] = 0
        while queue:
            curr = queue.popleft()
            for neighbor in graph[curr]:
                if distances[neighbor] == -1:
                    distances[neighbor] = distances[curr] + 1
                    queue.append(neighbor)
        return distances

    results = []
    for start, end, target in queries:
        # Find the unique path from start to end using DFS.
        path = find_path(start, end)
        # Compute distances from the target node using BFS.
        distances = bfs_from_target(target)
        # Determine the node on the path that is closest to the target.
        closest = path[0]
        min_dist = distances[closest]
        for node in path:
            if distances[node] < min_dist:
                min_dist = distances[node]
                closest = node
        results.append(closest)
    return results

# Example run:
n = 7
edges = [[0,1],[0,2],[0,3],[1,4],[2,5],[2,6]]
query = [[5,3,4],[5,3,6]]
print(closestNode(n, edges, query))  # Expected output: [0, 2]
← Back to All Questions