{x}
blog image

Closest Node to Path in Tree

Solution Explanation for Closest Node to Path in Tree

This problem involves finding the closest node to a given node within a path in a tree. We'll break down the solution into steps and provide code examples in Python.

1. Building the Tree:

First, we need to represent the tree structure. We can do this using an adjacency list:

def build_tree(n, edges):
    tree = [[] for _ in range(n)]
    for u, v in edges:
        tree[u].append(v)
        tree[v].append(u)  # Bidirectional edges
    return tree

2. Finding the Path:

We need a function to find the path between two nodes (start and end) in the tree. We can use Breadth-First Search (BFS) for this:

from collections import deque
 
def find_path(tree, start, end):
    queue = deque([(start, [start])])  # (node, path_so_far)
    visited = {start}
    while queue:
        node, path = queue.popleft()
        if node == end:
            return path
        for neighbor in tree[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, path + [neighbor]))
    return None  # No path found

3. Finding the Closest Node:

Now, we need to find the node on the path that's closest to the query node (node_i). We'll do this using Breadth-First Search again, starting from node_i:

def closest_node(tree, node_i, path):
    queue = deque([(node_i, 0)])  # (node, distance)
    visited = {node_i}
    closest_node_on_path = None
    min_distance = float('inf')
    while queue:
        node, distance = queue.popleft()
        if node in path:
            if distance < min_distance:
                min_distance = distance
                closest_node_on_path = node
        for neighbor in tree[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, distance + 1))
    return closest_node_on_path

4. Putting it Together:

Finally, we combine these functions to solve the main problem:

def closest_node_to_path(n, edges, query):
    tree = build_tree(n, edges)
    result = []
    for start, end, node_i in query:
        path = find_path(tree, start, end)
        if path:
            closest = closest_node(tree, node_i, path)
            result.append(closest)
        else:
            result.append(-1) #Handle case where no path exists.
    return result

Example Usage:

n = 7
edges = [[0, 1], [0, 2], [0, 3], [1, 4], [2, 5], [2, 6]]
query = [[5, 3, 4], [5, 3, 6]]
answer = closest_node_to_path(n, edges, query)
print(answer)  # Output: [0, 2]
 
n = 3
edges = [[0, 1], [1, 2]]
query = [[0, 1, 2]]
answer = closest_node_to_path(n, edges, query)
print(answer) # Output: [1]

Time Complexity Analysis:

  • build_tree: O(E), where E is the number of edges (approximately n-1 in a tree).
  • find_path: O(V+E), where V is the number of vertices (n in this case). BFS visits each node and edge at most once.
  • closest_node: O(V+E) in the worst case (BFS again).
  • Overall: The dominant factor is the nested loop structure implied by processing each query. Therefore, the overall time complexity is O(Q * (V+E)), where Q is the number of queries. Since E is proportional to V in a tree, this simplifies to O(Q * V).

Space Complexity Analysis:

The space complexity is dominated by the queue in the BFS functions and the visited set which are O(V) in the worst case. Therefore, the overall space complexity is O(V).

This detailed explanation, including code and complexity analysis, provides a comprehensive solution to the "Closest Node to Path in Tree" problem. Remember to adapt the code to other languages as needed, but the core algorithms (BFS for pathfinding and BFS for finding the closest node) remain the same.