Closest Node to Path in Tree

Problem#

You are given an unrooted tree of N nodes and a list of queries (s, t, target). For each query, return the node lying on the path from s to t whose distance to target is minimum. This is an curriculum variant of LeetCode tree-path queries.

Examples#

Path tree 0 - 1 - 2 - 3, query (0, 3, 2) → 2 (target is already on the path).
Star tree with center 0, leaves 1, 2, 3, query (1, 2, 3) → 0 (only 0 is on both paths).

Constraints#

1 <= N <= 10^4, 1 <= Q <= 10^4.

Hints#

Hint 1

BFS from target first to label dist[v] for every node.

Hint 2

Recover the s -> t path by parent-tracing a second BFS from s, then pick the minimum-dist node on it.

Approach#

For each query: BFS from target to compute distances; BFS from s recording parents to recover the path to t. Walk that path and return the node with smallest distance to target.

Solution#

class Solution {
public:
    int closestNode(int N, vector<vector<int>>& edges, int s, int t, int target) {
        vector<vector<int>> g(N);
        for (auto& e : edges) { g[e[0]].push_back(e[1]); g[e[1]].push_back(e[0]); }
        vector<int> distTarget = bfsDist(g, N, target);
        vector<int> parent = bfsParent(g, N, s);
        // Reconstruct s -> t path.
        vector<int> path;
        for (int v = t; v != -1; v = parent[v]) path.push_back(v);
        // Find min distance node on path.
        int best = path[0], bestD = distTarget[path[0]];
        for (int v : path) if (distTarget[v] < bestD) { bestD = distTarget[v]; best = v; }
        return best;
    }
private:
    vector<int> bfsDist(vector<vector<int>>& g, int N, int src) {
        vector<int> d(N, -1);
        queue<int> q; q.push(src); d[src] = 0;
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int v : g[u]) if (d[v] == -1) { d[v] = d[u] + 1; q.push(v); }
        }
        return d;
    }
    vector<int> bfsParent(vector<vector<int>>& g, int N, int src) {
        vector<int> p(N, -1);
        vector<int> seen(N, 0);
        queue<int> q; q.push(src); seen[src] = 1;
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int v : g[u]) if (!seen[v]) { seen[v] = 1; p[v] = u; q.push(v); }
        }
        return p;
    }
};

func closestNode(N int, edges [][]int, s int, t int, target int) int {
    g := make([][]int, N)
    for _, e := range edges {
        g[e[0]] = append(g[e[0]], e[1])
        g[e[1]] = append(g[e[1]], e[0])
    }
    bfsDist := func(src int) []int {
        d := make([]int, N)
        for i := range d {
            d[i] = -1
        }
        d[src] = 0
        q := []int{src}
        for len(q) > 0 {
            u := q[0]
            q = q[1:]
            for _, v := range g[u] {
                if d[v] == -1 {
                    d[v] = d[u] + 1
                    q = append(q, v)
                }
            }
        }
        return d
    }
    bfsParent := func(src int) []int {
        p := make([]int, N)
        for i := range p {
            p[i] = -1
        }
        seen := make([]bool, N)
        seen[src] = true
        q := []int{src}
        for len(q) > 0 {
            u := q[0]
            q = q[1:]
            for _, v := range g[u] {
                if !seen[v] {
                    seen[v] = true
                    p[v] = u
                    q = append(q, v)
                }
            }
        }
        return p
    }
    distTarget := bfsDist(target)
    parent := bfsParent(s)
    path := []int{}
    for v := t; v != -1; v = parent[v] {
        path = append(path, v)
    }
    best, bestD := path[0], distTarget[path[0]]
    for _, v := range path {
        if distTarget[v] < bestD {
            bestD = distTarget[v]
            best = v
        }
    }
    return best
}

from collections import deque
from typing import List

class Solution:
    def closestNode(self, N: int, edges: List[List[int]], s: int, t: int, target: int) -> int:
        g: List[List[int]] = [[] for _ in range(N)]
        for a, b in edges:
            g[a].append(b)
            g[b].append(a)

        def bfs_dist(src: int) -> List[int]:
            d = [-1] * N
            d[src] = 0
            q = deque([src])
            while q:
                u = q.popleft()
                for v in g[u]:
                    if d[v] == -1:
                        d[v] = d[u] + 1
                        q.append(v)
            return d

        def bfs_parent(src: int) -> List[int]:
            p = [-1] * N
            seen = [False] * N
            seen[src] = True
            q = deque([src])
            while q:
                u = q.popleft()
                for v in g[u]:
                    if not seen[v]:
                        seen[v] = True
                        p[v] = u
                        q.append(v)
            return p

        dist_target = bfs_dist(target)
        parent = bfs_parent(s)
        path: List[int] = []
        v = t
        while v != -1:
            path.append(v)
            v = parent[v]
        best, best_d = path[0], dist_target[path[0]]
        for v in path:
            if dist_target[v] < best_d:
                best_d = dist_target[v]
                best = v
        return best

var closestNode = function(N, edges, s, t, target) {
    const g = Array.from({ length: N }, () => []);
    for (const [a, b] of edges) {
        g[a].push(b);
        g[b].push(a);
    }
    const bfsDist = (src) => {
        const d = new Array(N).fill(-1);
        d[src] = 0;
        const q = [src];
        let head = 0;
        while (head < q.length) {
            const u = q[head++];
            for (const v of g[u]) {
                if (d[v] === -1) {
                    d[v] = d[u] + 1;
                    q.push(v);
                }
            }
        }
        return d;
    };
    const bfsParent = (src) => {
        const p = new Array(N).fill(-1);
        const seen = new Array(N).fill(false);
        seen[src] = true;
        const q = [src];
        let head = 0;
        while (head < q.length) {
            const u = q[head++];
            for (const v of g[u]) {
                if (!seen[v]) {
                    seen[v] = true;
                    p[v] = u;
                    q.push(v);
                }
            }
        }
        return p;
    };
    const distTarget = bfsDist(target);
    const parent = bfsParent(s);
    const path = [];
    for (let v = t; v !== -1; v = parent[v]) path.push(v);
    let best = path[0], bestD = distTarget[path[0]];
    for (const v of path) {
        if (distTarget[v] < bestD) {
            bestD = distTarget[v];
            best = v;
        }
    }
    return best;
};

class Solution {
    private List<List<Integer>> g;
    private int N;

    public int closestNode(int N, int[][] edges, int s, int t, int target) {
        this.N = N;
        g = new ArrayList<>();
        for (int i = 0; i < N; i++) g.add(new ArrayList<>());
        for (int[] e : edges) {
            g.get(e[0]).add(e[1]);
            g.get(e[1]).add(e[0]);
        }
        int[] distTarget = bfsDist(target);
        int[] parent = bfsParent(s);
        List<Integer> path = new ArrayList<>();
        for (int v = t; v != -1; v = parent[v]) path.add(v);
        int best = path.get(0), bestD = distTarget[path.get(0)];
        for (int v : path) {
            if (distTarget[v] < bestD) {
                bestD = distTarget[v];
                best = v;
            }
        }
        return best;
    }

    private int[] bfsDist(int src) {
        int[] d = new int[N];
        Arrays.fill(d, -1);
        d[src] = 0;
        Deque<Integer> q = new ArrayDeque<>();
        q.offer(src);
        while (!q.isEmpty()) {
            int u = q.poll();
            for (int v : g.get(u)) {
                if (d[v] == -1) {
                    d[v] = d[u] + 1;
                    q.offer(v);
                }
            }
        }
        return d;
    }

    private int[] bfsParent(int src) {
        int[] p = new int[N];
        Arrays.fill(p, -1);
        boolean[] seen = new boolean[N];
        seen[src] = true;
        Deque<Integer> q = new ArrayDeque<>();
        q.offer(src);
        while (!q.isEmpty()) {
            int u = q.poll();
            for (int v : g.get(u)) {
                if (!seen[v]) {
                    seen[v] = true;
                    p[v] = u;
                    q.offer(v);
                }
            }
        }
        return p;
    }
}

function closestNode(N: number, edges: number[][], s: number, t: number, target: number): number {
    const g: number[][] = Array.from({ length: N }, () => []);
    for (const [a, b] of edges) {
        g[a].push(b);
        g[b].push(a);
    }
    const bfsDist = (src: number): number[] => {
        const d: number[] = new Array(N).fill(-1);
        d[src] = 0;
        const q: number[] = [src];
        let head = 0;
        while (head < q.length) {
            const u = q[head++];
            for (const v of g[u]) {
                if (d[v] === -1) {
                    d[v] = d[u] + 1;
                    q.push(v);
                }
            }
        }
        return d;
    };
    const bfsParent = (src: number): number[] => {
        const p: number[] = new Array(N).fill(-1);
        const seen: boolean[] = new Array(N).fill(false);
        seen[src] = true;
        const q: number[] = [src];
        let head = 0;
        while (head < q.length) {
            const u = q[head++];
            for (const v of g[u]) {
                if (!seen[v]) {
                    seen[v] = true;
                    p[v] = u;
                    q.push(v);
                }
            }
        }
        return p;
    };
    const distTarget = bfsDist(target);
    const parent = bfsParent(s);
    const path: number[] = [];
    for (let v = t; v !== -1; v = parent[v]) path.push(v);
    let best = path[0], bestD = distTarget[path[0]];
    for (const v of path) {
        if (distTarget[v] < bestD) {
            bestD = distTarget[v];
            best = v;
        }
    }
    return best;
}

Editorial#

The path between two nodes in a tree is unique, so a single BFS-with-parents from s lets us reconstruct it. Pre-computing distances from target once per query lets the path walk be a linear scan. If queries share target, the distance BFS can be cached for a larger speedup.

Complexity#

Time: O((N + Q) * N).
Space: O(N).

Problem#

Examples#

Constraints#

Hints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Keyboard shortcuts

Problem#

Examples#

Constraints#

Hints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Related#