Closest Node to Path in Tree - Practice Coding Problems

Closest Node to Path in Tree - Problem

Imagine you're building a GPS navigation system for a tree-structured network where locations are connected by bidirectional roads, forming a perfect tree (no cycles, exactly n-1 edges for n nodes).

You're given:

n nodes numbered from 0 to n-1
edges array defining the tree structure
Multiple queries, each asking: "On the path from point A to point B, which location is closest to point C?"

For each query [start, end, target], you need to find the node on the unique path from start to end that has the minimum distance to the target node.

Goal: Return an array where each element is the closest node on the respective query path.

Input & Output

example_1.py — Basic Tree

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

› Output: [0, 0]

💡 Note: For query [5,3,4]: Path from 5 to 3 is [5,0,1,3]. Distances: 5→4 is 3, 0→4 is 1, 1→4 is 2, 3→4 is 2. Node 0 has minimum distance 1. For query [5,3,6]: Same path [5,0,1,3]. Distances: 5→6 is 2, 0→6 is 1, 1→6 is 2, 3→6 is 3. Node 0 has minimum distance 1.

example_2.py — Linear Tree

$ Input: n = 4, edges = [[0,1],[1,2],[2,3]], queries = [[0,3,1]]

› Output: [1]

💡 Note: For query [0,3,1]: Path from 0 to 3 is [0,1,2,3]. Distances: 0→1 is 1, 1→1 is 0, 2→1 is 1, 3→1 is 2. Node 1 has minimum distance 0.

example_3.py — Single Node Path

$ Input: n = 3, edges = [[0,1],[1,2]], queries = [[1,1,0]]

› Output: [1]

💡 Note: For query [1,1,0]: Path from 1 to 1 is just [1]. Distance 1→0 is 1. So node 1 is the answer.

Constraints

2 ≤ n ≤ 10⁵
edges.length == n - 1
edges[i].length == 2
0 ≤ node1_i, node2_i ≤ n - 1
The input represents a valid tree
1 ≤ queries.length ≤ 10⁵
query[i].length == 3
0 ≤ start_i, end_i, node_i ≤ n - 1

Visualization

Tap to expand

Understanding the Visualization

Build Trail Map

Create the tree structure representing trail connections between lodges and camps

Query Processing

For each query 'find closest point to C on trail A→B', locate the unique path

Distance Calculation

Check every point on the A→B trail and measure hiking distance to destination C

Optimal Meeting Point

Return the trail point with minimum hiking distance to the target location

Key Takeaway

🎯 Key Insight: In a tree, there's exactly one path between any two nodes. We find this path and check the distance from each path node to our target, returning the node with minimum distance.

Asked in

G Google 42 f Meta 38 a Amazon 31 ⊞ Microsoft 28

The optimal approach uses LCA (Lowest Common Ancestor) preprocessing with binary lifting to efficiently find paths and calculate distances. After O(n log n) preprocessing, each query can be answered in O(n + log n) time by finding the path via LCA and checking distances from each path node to the target.

Common Approaches

Approach	Time	Space	Notes
✓ LCA with Distance Preprocessing	O(n log n + m * n)	O(n log n)	Preprocess tree with LCA and distance arrays, then efficiently answer queries
Brute Force (BFS for each query)	O(m * n²)	O(n)	For each query, find the path using BFS, then check distance from each path node to target

LCA with Distance Preprocessing — Algorithm Steps

Preprocess tree: build parent arrays and depths using DFS
For each query, find LCA of start and end to get the path
Extract all nodes on the path from start to end via LCA
For each path node, calculate distance to target using LCA
Return the path node with minimum distance to target

Visualization

Tap to expand

Step-by-Step Walkthrough

Preprocess Tree

Build parent arrays and depth information using DFS

Find LCA

Use binary lifting to find lowest common ancestor of start and end

Extract Path

Path goes from start→LCA→end, extract all nodes on this path

Calculate Distances

For each path node, calculate distance to target using LCA

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <math.h>

#define MAX_N 1005
#define MAX_LOG 20

int graph[MAX_N][MAX_N];
int graphSize[MAX_N];
int parent[MAX_N][MAX_LOG];
int depth[MAX_N];
int LOG_VAL;

void dfs(int node, int par, int d) {
    parent[node][0] = par;
    depth[node] = d;
    
    for (int i = 0; i < graphSize[node]; i++) {
        int neighbor = graph[node][i];
        if (neighbor != par) {
            dfs(neighbor, node, d + 1);
        }
    }
}

int lca(int u, int v) {
    if (depth[u] < depth[v]) {
        int temp = u; u = v; v = temp;
    }
    
    // Bring u to same level as v
    int diff = depth[u] - depth[v];
    for (int i = 0; i < LOG_VAL; i++) {
        if ((diff >> i) & 1) {
            u = parent[u][i];
        }
    }
    
    if (u == v) return u;
    
    // Binary lifting
    for (int i = LOG_VAL - 1; i >= 0; i--) {
        if (parent[u][i] != parent[v][i]) {
            u = parent[u][i];
            v = parent[v][i];
        }
    }
    
    return parent[u][0];
}

int distance(int u, int v) {
    return depth[u] + depth[v] - 2 * depth[lca(u, v)];
}

int getPath(int start, int end, int* path) {
    int lcaNode = lca(start, end);
    int pathSize = 0;
    
    // Path from start to lca
    int curr = start;
    while (curr != lcaNode) {
        path[pathSize++] = curr;
        curr = parent[curr][0];
    }
    path[pathSize++] = lcaNode;
    
    // Path from lca to end (collect in temp array)
    int temp[MAX_N];
    int tempSize = 0;
    curr = end;
    while (curr != lcaNode) {
        temp[tempSize++] = curr;
        curr = parent[curr][0];
    }
    
    // Add temp in reverse order
    for (int i = tempSize - 1; i >= 0; i--) {
        path[pathSize++] = temp[i];
    }
    
    return pathSize;
}

int* closestNode(int n, int** edges, int edgesSize, int** queries, int queriesSize, int* returnSize) {
    // Initialize
    LOG_VAL = (int)log2(n) + 1;
    
    for (int i = 0; i < n; i++) {
        graphSize[i] = 0;
        for (int j = 0; j < LOG_VAL; j++) {
            parent[i][j] = -1;
        }
    }
    
    // Build adjacency list
    for (int i = 0; i < edgesSize; i++) {
        int u = edges[i][0], v = edges[i][1];
        graph[u][graphSize[u]++] = v;
        graph[v][graphSize[v]++] = u;
    }
    
    // Root the tree at node 0
    dfs(0, -1, 0);
    
    // Fill parent table for binary lifting
    for (int j = 1; j < LOG_VAL; j++) {
        for (int i = 0; i < n; i++) {
            if (parent[i][j-1] != -1) {
                parent[i][j] = parent[parent[i][j-1]][j-1];
            }
        }
    }
    
    int* result = (int*)malloc(queriesSize * sizeof(int));
    *returnSize = queriesSize;
    
    for (int i = 0; i < queriesSize; i++) {
        int start = queries[i][0];
        int end = queries[i][1];
        int target = queries[i][2];
        
        int path[MAX_N];
        int pathSize = getPath(start, end, path);
        
        int minDist = INT_MAX;
        int closest = path[0];
        
        for (int j = 0; j < pathSize; j++) {
            int dist = distance(path[j], target);
            if (dist < minDist) {
                minDist = dist;
                closest = path[j];
            }
        }
        
        result[i] = closest;
    }
    
    return result;
}

int main() {
    int n;
    scanf("%d", &n);
    // Parse input and call solution
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n + m * n)

O(n log n) preprocessing for LCA, O(n) per query for path and distance calculations

⚡ Linearithmic

Space Complexity

O(n log n)

Space for LCA binary lifting arrays and parent information

⚡ Linearithmic Space

67.2K Views

Medium-High Frequency

~25 min Avg. Time

1.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

LCA with Distance Preprocessing — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler