Closest Node to Path in Tree - Solution & Explanation

Problem Overview: You are given a tree and multiple queries. Each query provides three nodes (start, end, node). The goal is to find the node on the path between start and end whose distance to node is minimum. Since the graph is a tree, there is exactly one simple path between any two nodes, which makes path and ancestor relationships the key observation.

Approach 1: BFS Distance Check Per Query (O(q * n) time, O(n) space)

A straightforward approach computes distances from node using Breadth-First Search. For each query, first reconstruct the path between start and end using parent tracking or another BFS. Then iterate through every node on that path and pick the one with the smallest distance from node. This works because BFS gives shortest distances in a tree. The downside is cost: repeating BFS and path reconstruction for every query becomes expensive when the number of queries grows.

Approach 2: Explicit Path + Distance Comparison (O(q * n) time, O(n) space)

Another improvement builds the path from start to end using a single Depth-First Search. Once the path is extracted, compute distances from node using BFS or precomputed parent traversal. Iterate through nodes in the path and track the minimum distance. This approach clarifies the structure of the problem but still scans the path for every query. In the worst case the path length can approach n, which keeps the complexity high.

Approach 3: LCA Observation with Binary Lifting (O((n + q) log n) time, O(n log n) space)

The key insight comes from tree ancestry. The closest node on the path from start to end relative to node must be one of three candidates: lca(start, end), lca(start, node), or lca(end, node). Among these candidates, the correct answer is simply the one with the greatest depth in the tree. Intuitively, the deepest of these LCAs lies closest to the intersection of the two relevant paths.

Preprocess the tree using DFS to compute node depths and a binary lifting table for fast Lowest Common Ancestor queries. With this preprocessing, each lca() lookup runs in O(log n). For every query, compute the three LCAs and return the candidate with maximum depth. This reduces each query to a few constant-time comparisons after logarithmic ancestor jumps.

DFS preprocessing runs once in O(n log n) time and uses adjacency lists built from the Tree structure. Query handling is efficient even for large inputs.

Recommended for interviews: The binary lifting + LCA approach. Interviewers expect you to recognize that path relationships in a tree reduce to LCA computations. Mentioning the brute force BFS approach shows understanding of tree traversal, but deriving the three-LCA observation demonstrates stronger algorithmic insight and scales to large query counts.