Given a tree, find the kth node in the path from node 'a' to node 'b' in Log(n)?

Question

Given a tree, I need to find the 'k'th node in the path from 'a' to 'b'. That means that I need to find the node at the 'kth' position in the path from node 'a' to node 'b'. I was thinking on the lines of Lowest-common-ancestor and/or heavy-light decomposition but I'm not sure if that's the way to do it. Any guidance in the right direction is appreciated.

Details:

• The tree is NOT a binary tree. It's an undirected graph having n-1 edges, n vertices and no cycles. Just your regular tree
• The tree has vertices numbered from 1 to n. There are n-1 undirected edges connecting n-1 pairs of these vertices
• 'a' and 'b' are any 2 vertices numbered from 1 to n in the tree. We are to find the 'k'th node in the path from 'a' to 'b'. It is guaranteed that the value of 'k' is <= number of nodes in the path from 'a' to 'b'

A BFS applied on every query (kth node from 'a' to 'b') is not an option as the number of queries are large.

Answer 1

Do the lowest-common-ancestor, and keep for every node it's depth (distance to the root).

Next figure out if the k'th node is on the a to lca or lca to b part. The difference in depth is the number of nodes between them, so if depth[a] - depth[lca] > k then the node is on lca-b part.

If the node is on the a to lca part, just find the k'th ancestor of a. Should be log(N) using the LCA data you precalculated.

If the node is on the b to lca part, then you can compute k' which is the distance of the kth node from b (k' = 1 + depth[a] + depth[b] - 2*depth[lca] - k)) and then get k' ancestor of b (again easy with the the LCA data).

Overall all the lookups are logN and the other steps are constant so you do O(LogN) per query.