Is Closest Node to Path in Tree easy or hard?

Closest Node to Path in Tree is classified as Hard because it requires understanding of Lowest Common Ancestor techniques and tree path properties. The trick of reducing the answer to three LCA candidates is not immediately obvious without strong tree algorithm experience.

Closest Node to Path in Tree Python/Java solution

Most implementations preprocess the tree using DFS and a binary lifting table. Python, Java, C++, and Go versions follow the same structure: build adjacency lists, compute depth and parent tables, implement an LCA function, then evaluate three LCAs per query and return the deepest node.

How to solve Closest Node to Path in Tree in O(n)?

Pure O(n) per query is possible using BFS or DFS to compute distances and scanning the path between start and end. However, for multiple queries this becomes inefficient. Most implementations instead preprocess the tree and answer each query using LCA in O(log n), which scales much better.

What is the best approach for Closest Node to Path in Tree?

The best approach uses Lowest Common Ancestor (LCA) with binary lifting. For each query (start, end, node), compute lca(start, end), lca(start, node), and lca(end, node). The deepest of these three nodes is the closest node on the path between start and end to the target node. Preprocessing takes O(n log n) and each query runs in O(log n).

Is Closest Node to Path in Tree asked at Google/Amazon/Meta?

Tree queries involving LCA and path relationships appear frequently in interviews at companies like Google, Amazon, and Meta. Variants of this problem test your ability to preprocess trees, compute ancestors efficiently, and reason about path intersections.

What data structure is used in Closest Node to Path in Tree?

The solution relies on a tree represented with adjacency lists, along with a binary lifting table for ancestor jumps. DFS is used to compute node depth and parent relationships, and LCA queries determine how paths intersect.

What is the time complexity of Closest Node to Path in Tree?

The optimal solution runs in O((n + q) log n) time. A DFS preprocessing step builds depth information and the binary lifting ancestor table in O(n log n). Each query then performs three LCA computations, each taking O(log n).

Description Hints 3 Video 13:02

2277. Closest Node to Path in Tree

Hard62.1% acceptance1 companyPremium elsewhere, free here

You are given a positive integer n representing the number of nodes in a tree, numbered from 0 to n - 1 (inclusive). You are also given a 2D integer array edges of length n - 1, where edges[i] = [node1_i, node2_i] denotes that there is a bidirectional edge connecting node1_i and node2_i in the tree.

You are given a 0-indexed integer array query of length m where query[i] = [start_i, end_i, node_i] means that for the i^th query, you are tasked with finding the node on the path from start_i to end_i that is closest to node_i.

Return an integer array answer of length m, where answer[i] is the answer to the i^th query.

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]]
Output: [0,2]
Explanation:
The path from node 5 to node 3 consists of the nodes 5, 2, 0, and 3.
The distance between node 4 and node 0 is 2.
Node 0 is the node on the path closest to node 4, so the answer to the first query is 0.
The distance between node 6 and node 2 is 1.
Node 2 is the node on the path closest to node 6, so the answer to the second query is 2.

Example 2:

Input: n = 3, edges = [[0,1],[1,2]], query = [[0,1,2]]
Output: [1]
Explanation:
The path from node 0 to node 1 consists of the nodes 0, 1.
The distance between node 2 and node 1 is 1.
Node 1 is the node on the path closest to node 2, so the answer to the first query is 1.

Example 3:

Input: n = 3, edges = [[0,1],[1,2]], query = [[0,0,0]]
Output: [0]
Explanation:
The path from node 0 to node 0 consists of the node 0.
Since 0 is the only node on the path, the answer to the first query is 0.

Constraints:

1 <= n <= 1000
edges.length == n - 1
edges[i].length == 2
0 <= node1_i, node2_i <= n - 1
node1_i != node2_i
1 <= query.length <= 1000
query[i].length == 3
0 <= start_i, end_i, node_i <= n - 1
The graph is a tree.

Asked at 1 company

Google

Topics

Hints open one at a time

Hint 1

For the ith query, find the distance from node_i to every other node in the tree.

Hint 2

We can use a BFS to find the distances.

Hint 3

Use DFS to find all the nodes on the path from start_i to end_i.