Graph Theory37 sections · 1633 units
Open in Course

LCA in HLD

(Finding the meeting point)

During the path query walk, the LCA emerges naturally. When uu and vv end up in the same chain after the while loop, the one closer to the root is the LCA. If depth[u] < depth[v], then uu is the LCA. Otherwise, vv is the LCA.

You can store this value if needed. You do not need a separate LCA algorithm like binary lifting if you only need the LCA during path queries. HLD finds it as a byproduct of the path walk.