Tarjan's off-line lowest common ancestors algorithm

<h2 id="pseudocode">Pseudocode</h2>
The pseudocode below determines the lowest common ancestor of each pair in P, given the root r of a tree in which the children of node n are in the set n.children. For this offline algorithm, the set P must be specified in advance. It uses the MakeSet, Find, and Union functions of a <a href="/facts/Disjoint-set_data_structure/QnFQNedE">disjoint-set data structure</a>. MakeSet(u) removes u to a singleton set, Find(u) returns the standard representative of the set containing u, and Union(u,v) merges the set containing u with the set containing v.
TarjanOLCA(r) is first called on the root r.

function TarjanOLCA(u) is
 MakeSet(u)
 u.ancestor := u
 for each v in u.children do
 TarjanOLCA(v)
 Union(u, v)
 Find(u).ancestor := u
 u.color := black
 for each v such that {u, v} in P do
 if v.color == black then
 print "Tarjan's Lowest Common Ancestor of " + u +
 " and " + v + " is " + Find(v).ancestor + "."

Each node is initially white, and is colored black after it and all its children have been visited.
For each node pair {u,v} to be investigated:

<ul><li>When v is already black (viz. when v comes before u in a post-order traversal of the tree): After u is colored black, the lowest common ancestor of this pair is available as Find(v).ancestor, but only while the LCA of u and v is not colored black.</li>
<li>Otherwise: Once v is colored black, the LCA will be available as Find(u).ancestor, while the LCA is not colored black.</li></ul>
For reference, here are optimized versions of MakeSet, Find, and Union for a <a href="/facts/Disjoint-set_data_structure/QnFQNedE">disjoint-set forest</a>:

function MakeSet(x) is
 x.parent := x
 x.rank  := 1
 
function Union(x, y) is
 xRoot := Find(x)
 yRoot := Find(y)
 if xRoot.rank > yRoot.rank then
 yRoot.parent := xRoot
 else if xRoot.rank < yRoot.rank then
 xRoot.parent := yRoot
 else if xRoot.rank == yRoot.rank then
 yRoot.parent := xRoot
 xRoot.rank := xRoot.rank + 1
 
function Find(x) is
 if x.parent != x then
 x.parent := Find(x.parent)
 return x.parent

<h2 id="speeding-up-the-algorithm">Speeding up the algorithm</h2>
It is possible to preprocess the input LCA queries in such a manner, that the algorithm works faster by an order of magnitude. 

function Preprocess(P) is
 m := empty map
 for each {u, v} in P do
 if u is not mapped in m
 m[u] := ∅
 m[u] := m[u] ∪ {(u, v)}
 if v is not mapped in m
 m[v] := ∅
 m[v] := m[v] ∪ {(u, v)}
 return m

function GetOpposite(q, u) is
   if q[0] == u then
       return q[1]
   return q[0]

function FasterTarjanOLCA(u) is
   MakeSet(u)
   u.ancestor := u
   for each v in u.children do
       FasterTarjanOLCA(v)
       Union(u, v)
       Find(u).ancestor := u
   u.color := black
   if m[u] == nil then
       return
   for each q in m[u] do
       v := GetOpposite(q, u)
       if v != nil and v.color == black then
           print "LCA of " + u + " and " + v + " is " + Find(v).ancestor + "."

The idea in the optimization is associating nodes with their counterparts in the list of input queries.

<ul><li><a href="/facts/Harold_N._Gabow/gLt88dfp">Gabow, H. N.</a>; <a href="/facts/Robert_Tarjan/kn1pMCN0">Tarjan, R. E.</a> (1983), "A linear-time algorithm for a special case of disjoint set union", Proceedings of the 15th ACM Symposium on Theory of Computing (STOC), pp. 246–251, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1145%2F800061.808753">10.1145/800061.808753</a>, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0-89791-099-0.</li></ul>
<ul><li><a href="/facts/Robert_Tarjan/kn1pMCN0">Tarjan, R. E.</a> (1979), "Applications of path compression on balanced trees", <a href="/facts/Journal_of_the_ACM/qkIF9LLS">Journal of the ACM</a>, 26 (4): 690–715, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1145%2F322154.322161">10.1145/322154.322161</a>.</li></ul>
<h2 id="external-links">External links</h2>
<ul><li><a href="https://github.com/coderodde/CR.OfflineLCA/blob/main/src/main/java/com/github/coderodde/algo/lca/impl/FasterTarjansOfflineLCAAlgorithm.java">Optimized Java implementation</a></li></ul>

Tarjan's off-line lowest common ancestors algorithm open-in-new

Tarjan's off-line lowest common ancestors algorithm