Where Tarjan's Offline LCA Matters

Introduction

Pick any two nodes in a tree — say node 7 and node 11. Their lowest common ancestor (LCA) is the deepest node that is an ancestor of both: the point where their two paths up to the root converge.

LCA is everywhere in practice: it drives distance queries between nodes (the distance from u to v equals $\text{depth}(u) + \text{depth}(v) - 2\cdot\text{depth}(\text{LCA}(u,v))$ ), it underlies compiler control-flow analysis, and it powers database query optimizers working on hierarchical data. The question comes up not once, but in bulk: you have a tree with n nodes and q pairs, and you need all q answers.

The naive approach queries each pair independently. The most basic method — walk up from each node until the paths meet — costs O(depth) per query, which is $O(n)$ on a skewed tree. A classic binary lifting table brings each query to $O(\log n)$ , so q queries cost $O(q \log n)$ . That is good, but it still grows with both n and q.

Robert Tarjan's offline algorithm (1979) blows past that bound. If you are willing to collect all q queries first and answer them together rather than on-demand (that is, "offline"), a single DFS over the tree — enhanced with a Union-Find structure — resolves every query in $O(n + q \cdot \alpha(n))$ total time, where $\alpha$ is the inverse Ackermann function, effectively a constant in any realistic setting. For large batches that savings is enormous.

Try It

The demo below builds an 11-node tree and loads 5 batch LCA queries. Click Step to advance Tarjan's DFS one node at a time, or Run all to watch the full sweep. Answered queries light up immediately as the DFS visits their nodes.

<p class="hint">An 11-node tree with 5 batch LCA queries. The DFS visits nodes in order, merging sets with Union-Find. A query <b>(u,v)</b> is answered the moment the DFS finishes one of them and the other is already visited.</p>
<div class="layout">
  <svg id="tree-svg" viewBox="0 0 340 240" width="340" height="240"></svg>
  <div class="panel">
    <div class="panel-title">LCA Queries</div>
    <div id="query-list"></div>
    <div class="panel-title" style="margin-top:.7rem">DFS Log</div>
    <div id="log"></div>
  </div>
</div>
<div class="btns">
  <button id="btn-step" type="button">Step</button>
  <button id="btn-run" type="button">Run all</button>
  <button id="btn-reset" type="button" class="ghost">Reset</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
.layout { display: flex; gap: .8rem; align-items: flex-start; flex-wrap: wrap; }
#tree-svg { flex-shrink: 0; }
.panel { flex: 1; min-width: 160px; font-size: .83rem; }
.panel-title { font-weight: 700; font-size: .78rem; text-transform: uppercase;
               letter-spacing: .04em; color: #555; margin-bottom: .25rem; }
#query-list { display: flex; flex-direction: column; gap: .22rem; }
.qrow { padding: .2rem .4rem; border-radius: 5px; background: #eef1f5;
        border: 1px solid #d0d8e4; display: flex; gap: .4rem; align-items: center; }
.qrow.answered { background: #d4edda; border-color: #82c491; }
.qrow .qlabel { font-weight: 600; flex: 1; }
.qrow .qans { color: #1a7d3e; font-weight: 700; }
#log { font-size: .78rem; color: #333; max-height: 130px; overflow-y: auto;
       background: #f7f8fb; border: 1px solid #dde3ec; border-radius: 5px;
       padding: .3rem .5rem; }
.log-line { line-height: 1.5; }
.log-enter { color: #1d3557; }
.log-leave { color: #6a0572; }
.log-answer { color: #1a7d3e; font-weight: 600; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin-top: .6rem; }
button { font: 600 14px system-ui, sans-serif; padding: .4rem .85rem;
         border: 1px solid #1d3557; background: #1d3557; color: #fff;
         border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .45; cursor: default; }
.node circle { stroke-width: 1.6; }
.node text { font: 600 11px system-ui, sans-serif; pointer-events: none; }
.edge { stroke: #b0bec5; stroke-width: 1.6; fill: none; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// ── Tree definition ───────────────────────────────────────────────────────────
// Nodes 0..10 (0 = root). Edges: parent → [children]
const CHILDREN = {
  0: [1, 2],
  1: [3, 4],
  2: [5, 6],
  3: [7, 8],
  4: [9],
  5: [10],
  6: [], 7: [], 8: [], 9: [], 10: []
};
// Node positions in SVG (x, y) — hand-laid for clarity
const POS = [
  [170, 20],   // 0
  [90,  70],   // 1
  [250, 70],   // 2
  [45,  130],  // 3
  [135, 130],  // 4
  [210, 130],  // 5
  [290, 130],  // 6
  [20,  200],  // 7
  [70,  200],  // 8
  [135, 200],  // 9
  [210, 200],  // 10
];
// LCA queries: [u, v, expected_lca]
const QUERIES_DEF = [
  [7, 9, 1],
  [8, 10, 0],
  [3, 4, 1],
  [6, 5, 2],
  [7, 8, 3],
];

// ── Union-Find with ancestor label (Tarjan's original approach) ───────────────
// uf[]: path-compressed union-find parent array (for merging sets)
// ancestor[]: for each UF root, stores the node label representing that set's LCA
let uf, ancestor;
function ufInit(n) {
  uf = Array.from({length:n},(_,i)=>i);
  ancestor = Array.from({length:n},(_,i)=>i);
}
function find(x) { return uf[x]===x ? x : (uf[x]=find(uf[x])); }
// union(child, par): merge child's set into par's set; par becomes root; ancestor preserved
function union(child, par) {
  const rc=find(child), rp=find(par);
  if(rc===rp) return;
  uf[rc]=rp; // par's root stays root; ancestor[rp] already = par
}

// ── State ─────────────────────────────────────────────────────────────────────
let color, dfsStack, queries, done;

function init() {
  ufInit(11);
  color   = new Array(11).fill('white'); // white=unvisited,gray=active,black=finished
  queries = QUERIES_DEF.map(([u,v,lca]) => ({u,v,lca,ans:null}));
  done    = false;
  dfsStack = [{node:0, childIdx:0, phase:'enter'}];
  renderSVG();
  renderQueries();
  clearLog();
  document.getElementById('btn-step').disabled = false;
  document.getElementById('btn-run').disabled  = false;
}

// Returns indexes of unanswered queries involving node
function queryIndexesFor(node) {
  return queries.map((q,i)=>i).filter(i=>{
    const q=queries[i]; return (q.u===node||q.v===node) && q.ans===null;
  });
}

// Advance one DFS step; returns false when DFS is complete
function step() {
  if(dfsStack.length===0) { done=true; return false; }
  const frame = dfsStack[dfsStack.length-1];

  if(frame.phase==='enter') {
    const v=frame.node;
    ancestor[v]=v; // initialise own ancestor label
    color[v]='gray';
    addLog(fmt('Enter %v%', { v: v }), 'log-enter');
    frame.phase='children';
    frame.childIdx=0;
    renderSVG();
    return true;
  }

  if(frame.phase==='children') {
    const v=frame.node;
    const ch=CHILDREN[v];
    if(frame.childIdx < ch.length) {
      const child=ch[frame.childIdx++];
      dfsStack.push({node:child, phase:'enter', childIdx:0});
      return true;
    }
    // All children processed → leave
    frame.phase='leave';
  }

  if(frame.phase==='leave') {
    const v=frame.node;
    color[v]='black';
    // For each finished child, merge child's set into v's set; v's ancestor label stays v
    // (This was already done when we returned from each child below, but we also do  it here for the iterative simulation: merge happens after child finishes.)
    const par=getParent(v);
    if(par!==null) {
      union(v, par);           // v's root folds into par's root
      ancestor[find(par)]=par; // root of merged set labels itself as par
    }
    // Answer pending queries involving v where the other node is already finished
    const idxs=queryIndexesFor(v);
    for(const i of idxs){
      const q=queries[i];
      const other = q.u===v ? q.v : q.u;
      if(color[other]==='black') {
        q.ans = ancestor[find(other)];
        addLog(`LCA(${q.u},${q.v}) = ${q.ans}`, 'log-answer');
      }
    }
    addLog(fmt('Leave %v%', { v: v }), 'log-leave');
    dfsStack.pop();
    renderSVG();
    renderQueries();
    return true;
  }
  return false;
}

function getParent(v) {
  for(const [p, ch] of Object.entries(CHILDREN)) {
    if(ch.includes(v)) return parseInt(p,10);
  }
  return null;
}

// ── Rendering ─────────────────────────────────────────────────────────────────
const NODE_R = 14;
const NODE_COLORS = { white:'#e8eef3', gray:'#f0a500', black:'#1d3557' };
const NODE_TEXT   = { white:'#1d3557', gray:'#fff',    black:'#fff'    };

function renderSVG() {
  const svg = document.getElementById('tree-svg');
  svg.innerHTML = '';
  // Draw edges first
  for(const [p, children] of Object.entries(CHILDREN)) {
    const [px,py] = POS[parseInt(p,10)];
    for(const c of children) {
      const [cx,cy] = POS[c];
      const line = document.createElementNS('http://www.w3.org/2000/svg','line');
      line.setAttribute('x1',px); line.setAttribute('y1',py+NODE_R);
      line.setAttribute('x2',cx); line.setAttribute('y2',cy-NODE_R);
      line.setAttribute('class','edge');
      svg.appendChild(line);
    }
  }
  // Draw nodes
  for(let i=0;i<11;i++){
    const [x,y]=POS[i]; const st=color[i];
    const g = document.createElementNS('http://www.w3.org/2000/svg','g');
    g.setAttribute('class','node');
    const circ = document.createElementNS('http://www.w3.org/2000/svg','circle');
    circ.setAttribute('cx',x); circ.setAttribute('cy',y); circ.setAttribute('r',NODE_R);
    circ.setAttribute('fill', NODE_COLORS[st]);
    circ.setAttribute('stroke', st==='white'?'#7a9bb5':'#1d3557');
    const txt = document.createElementNS('http://www.w3.org/2000/svg','text');
    txt.setAttribute('x',x); txt.setAttribute('y',y+4.5);
    txt.setAttribute('text-anchor','middle');
    txt.setAttribute('fill',NODE_TEXT[st]);
    txt.textContent=i;
    g.appendChild(circ); g.appendChild(txt);
    svg.appendChild(g);
  }
}

function renderQueries() {
  const el=document.getElementById('query-list');
  el.innerHTML='';
  queries.forEach((q,i)=>{
    const row=document.createElement('div');
    row.className='qrow'+(q.ans!==null?' answered':'');
    const label=document.createElement('span');
    label.className='qlabel';
    label.textContent=`LCA(${q.u}, ${q.v})`;
    row.appendChild(label);
    if(q.ans!==null){
      const ans=document.createElement('span');
      ans.className='qans';
      ans.textContent=`= ${q.ans}`;
      row.appendChild(ans);
    } else {
      const pending=document.createElement('span');
      pending.style.color='#888';
      pending.textContent='pending';
      row.appendChild(pending);
    }
    el.appendChild(row);
  });
}

function addLog(msg, cls) {
  const el=document.getElementById('log');
  const line=document.createElement('div');
  line.className='log-line '+cls;
  line.textContent=msg;
  el.appendChild(line);
  el.scrollTop=el.scrollHeight;
}
function clearLog(){ document.getElementById('log').innerHTML=''; }

// ── Controls ──────────────────────────────────────────────────────────────────
document.getElementById('btn-step').addEventListener('click', ()=>{
  if(!step()) {
    document.getElementById('btn-step').disabled=true;
    document.getElementById('btn-run').disabled=true;
    addLog('DFS complete.', 'log-leave');
  }
});
document.getElementById('btn-run').addEventListener('click', ()=>{
  let iterations=0;
  while(dfsStack.length>0 && iterations++<500) step();
  document.getElementById('btn-step').disabled=true;
  document.getElementById('btn-run').disabled=true;
  addLog('DFS complete.', 'log-leave');
  renderSVG(); renderQueries();
});
document.getElementById('btn-reset').addEventListener('click', init);

init();

// ── Startup verification (brute-force cross-check, errors in console) ─────────
(function verify(){
  const par={};
  function dfs(v,p){par[v]=p; for(const c of (CHILDREN[v]||[])) dfs(c,v);}
  dfs(0,null);
  function lcaBrute(u,v){
    const a=new Set(); let x=u;
    while(x!==null){a.add(x);x=par[x];}
    let y=v; while(!a.has(y)) y=par[y]; return y;
  }
  QUERIES_DEF.forEach(([u,v,expected])=>{
    const got=lcaBrute(u,v);
    if(got!==expected) console.error(fmt('LCA(%u%,%v%): expected %expected% got %got%', { u: u, v: v, expected: expected, got: got }));
  });
  console.log('Startup: all LCA expected values verified against brute-force.');
})();

<p class="hint">An 11-node tree with 5 batch LCA queries. The DFS visits nodes in order, merging sets with Union-Find. A query <b>(u,v)</b> is answered the moment the DFS finishes one of them and the other is already visited.</p>
<div class="layout">
  <svg id="tree-svg" viewBox="0 0 340 240" width="340" height="240"></svg>
  <div class="panel">
    <div class="panel-title">LCA Queries</div>
    <div id="query-list"></div>
    <div class="panel-title" style="margin-top:.7rem">DFS Log</div>
    <div id="log"></div>
  </div>
</div>
<div class="btns">
  <button id="btn-step" type="button">Step</button>
  <button id="btn-run" type="button">Run all</button>
  <button id="btn-reset" type="button" class="ghost">Reset</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
.layout { display: flex; gap: .8rem; align-items: flex-start; flex-wrap: wrap; }
#tree-svg { flex-shrink: 0; }
.panel { flex: 1; min-width: 160px; font-size: .83rem; }
.panel-title { font-weight: 700; font-size: .78rem; text-transform: uppercase;
               letter-spacing: .04em; color: #555; margin-bottom: .25rem; }
#query-list { display: flex; flex-direction: column; gap: .22rem; }
.qrow { padding: .2rem .4rem; border-radius: 5px; background: #eef1f5;
        border: 1px solid #d0d8e4; display: flex; gap: .4rem; align-items: center; }
.qrow.answered { background: #d4edda; border-color: #82c491; }
.qrow .qlabel { font-weight: 600; flex: 1; }
.qrow .qans { color: #1a7d3e; font-weight: 700; }
#log { font-size: .78rem; color: #333; max-height: 130px; overflow-y: auto;
       background: #f7f8fb; border: 1px solid #dde3ec; border-radius: 5px;
       padding: .3rem .5rem; }
.log-line { line-height: 1.5; }
.log-enter { color: #1d3557; }
.log-leave { color: #6a0572; }
.log-answer { color: #1a7d3e; font-weight: 600; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin-top: .6rem; }
button { font: 600 14px system-ui, sans-serif; padding: .4rem .85rem;
         border: 1px solid #1d3557; background: #1d3557; color: #fff;
         border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .45; cursor: default; }
.node circle { stroke-width: 1.6; }
.node text { font: 600 11px system-ui, sans-serif; pointer-events: none; }
.edge { stroke: #b0bec5; stroke-width: 1.6; fill: none; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// ── Tree definition ───────────────────────────────────────────────────────────
// Nodes 0..10 (0 = root). Edges: parent → [children]
const CHILDREN = {
  0: [1, 2],
  1: [3, 4],
  2: [5, 6],
  3: [7, 8],
  4: [9],
  5: [10],
  6: [], 7: [], 8: [], 9: [], 10: []
};
// Node positions in SVG (x, y) — hand-laid for clarity
const POS = [
  [170, 20],   // 0
  [90,  70],   // 1
  [250, 70],   // 2
  [45,  130],  // 3
  [135, 130],  // 4
  [210, 130],  // 5
  [290, 130],  // 6
  [20,  200],  // 7
  [70,  200],  // 8
  [135, 200],  // 9
  [210, 200],  // 10
];
// LCA queries: [u, v, expected_lca]
const QUERIES_DEF = [
  [7, 9, 1],
  [8, 10, 0],
  [3, 4, 1],
  [6, 5, 2],
  [7, 8, 3],
];

// ── Union-Find with ancestor label (Tarjan's original approach) ───────────────
// uf[]: path-compressed union-find parent array (for merging sets)
// ancestor[]: for each UF root, stores the node label representing that set's LCA
let uf, ancestor;
function ufInit(n) {
  uf = Array.from({length:n},(_,i)=>i);
  ancestor = Array.from({length:n},(_,i)=>i);
}
function find(x) { return uf[x]===x ? x : (uf[x]=find(uf[x])); }
// union(child, par): merge child's set into par's set; par becomes root; ancestor preserved
function union(child, par) {
  const rc=find(child), rp=find(par);
  if(rc===rp) return;
  uf[rc]=rp; // par's root stays root; ancestor[rp] already = par
}

// ── State ─────────────────────────────────────────────────────────────────────
let color, dfsStack, queries, done;

function init() {
  ufInit(11);
  color   = new Array(11).fill('white'); // white=unvisited,gray=active,black=finished
  queries = QUERIES_DEF.map(([u,v,lca]) => ({u,v,lca,ans:null}));
  done    = false;
  dfsStack = [{node:0, childIdx:0, phase:'enter'}];
  renderSVG();
  renderQueries();
  clearLog();
  document.getElementById('btn-step').disabled = false;
  document.getElementById('btn-run').disabled  = false;
}

// Returns indexes of unanswered queries involving node
function queryIndexesFor(node) {
  return queries.map((q,i)=>i).filter(i=>{
    const q=queries[i]; return (q.u===node||q.v===node) && q.ans===null;
  });
}

// Advance one DFS step; returns false when DFS is complete
function step() {
  if(dfsStack.length===0) { done=true; return false; }
  const frame = dfsStack[dfsStack.length-1];

  if(frame.phase==='enter') {
    const v=frame.node;
    ancestor[v]=v; // initialise own ancestor label
    color[v]='gray';
    addLog(fmt('Enter %v%', { v: v }), 'log-enter');
    frame.phase='children';
    frame.childIdx=0;
    renderSVG();
    return true;
  }

  if(frame.phase==='children') {
    const v=frame.node;
    const ch=CHILDREN[v];
    if(frame.childIdx < ch.length) {
      const child=ch[frame.childIdx++];
      dfsStack.push({node:child, phase:'enter', childIdx:0});
      return true;
    }
    // All children processed → leave
    frame.phase='leave';
  }

  if(frame.phase==='leave') {
    const v=frame.node;
    color[v]='black';
    // For each finished child, merge child's set into v's set; v's ancestor label stays v
    // (This was already done when we returned from each child below, but we also do  it here for the iterative simulation: merge happens after child finishes.)
    const par=getParent(v);
    if(par!==null) {
      union(v, par);           // v's root folds into par's root
      ancestor[find(par)]=par; // root of merged set labels itself as par
    }
    // Answer pending queries involving v where the other node is already finished
    const idxs=queryIndexesFor(v);
    for(const i of idxs){
      const q=queries[i];
      const other = q.u===v ? q.v : q.u;
      if(color[other]==='black') {
        q.ans = ancestor[find(other)];
        addLog(`LCA(${q.u},${q.v}) = ${q.ans}`, 'log-answer');
      }
    }
    addLog(fmt('Leave %v%', { v: v }), 'log-leave');
    dfsStack.pop();
    renderSVG();
    renderQueries();
    return true;
  }
  return false;
}

function getParent(v) {
  for(const [p, ch] of Object.entries(CHILDREN)) {
    if(ch.includes(v)) return parseInt(p,10);
  }
  return null;
}

// ── Rendering ─────────────────────────────────────────────────────────────────
const NODE_R = 14;
const NODE_COLORS = { white:'#e8eef3', gray:'#f0a500', black:'#1d3557' };
const NODE_TEXT   = { white:'#1d3557', gray:'#fff',    black:'#fff'    };

function renderSVG() {
  const svg = document.getElementById('tree-svg');
  svg.innerHTML = '';
  // Draw edges first
  for(const [p, children] of Object.entries(CHILDREN)) {
    const [px,py] = POS[parseInt(p,10)];
    for(const c of children) {
      const [cx,cy] = POS[c];
      const line = document.createElementNS('http://www.w3.org/2000/svg','line');
      line.setAttribute('x1',px); line.setAttribute('y1',py+NODE_R);
      line.setAttribute('x2',cx); line.setAttribute('y2',cy-NODE_R);
      line.setAttribute('class','edge');
      svg.appendChild(line);
    }
  }
  // Draw nodes
  for(let i=0;i<11;i++){
    const [x,y]=POS[i]; const st=color[i];
    const g = document.createElementNS('http://www.w3.org/2000/svg','g');
    g.setAttribute('class','node');
    const circ = document.createElementNS('http://www.w3.org/2000/svg','circle');
    circ.setAttribute('cx',x); circ.setAttribute('cy',y); circ.setAttribute('r',NODE_R);
    circ.setAttribute('fill', NODE_COLORS[st]);
    circ.setAttribute('stroke', st==='white'?'#7a9bb5':'#1d3557');
    const txt = document.createElementNS('http://www.w3.org/2000/svg','text');
    txt.setAttribute('x',x); txt.setAttribute('y',y+4.5);
    txt.setAttribute('text-anchor','middle');
    txt.setAttribute('fill',NODE_TEXT[st]);
    txt.textContent=i;
    g.appendChild(circ); g.appendChild(txt);
    svg.appendChild(g);
  }
}

function renderQueries() {
  const el=document.getElementById('query-list');
  el.innerHTML='';
  queries.forEach((q,i)=>{
    const row=document.createElement('div');
    row.className='qrow'+(q.ans!==null?' answered':'');
    const label=document.createElement('span');
    label.className='qlabel';
    label.textContent=`LCA(${q.u}, ${q.v})`;
    row.appendChild(label);
    if(q.ans!==null){
      const ans=document.createElement('span');
      ans.className='qans';
      ans.textContent=`= ${q.ans}`;
      row.appendChild(ans);
    } else {
      const pending=document.createElement('span');
      pending.style.color='#888';
      pending.textContent='pending';
      row.appendChild(pending);
    }
    el.appendChild(row);
  });
}

function addLog(msg, cls) {
  const el=document.getElementById('log');
  const line=document.createElement('div');
  line.className='log-line '+cls;
  line.textContent=msg;
  el.appendChild(line);
  el.scrollTop=el.scrollHeight;
}
function clearLog(){ document.getElementById('log').innerHTML=''; }

// ── Controls ──────────────────────────────────────────────────────────────────
document.getElementById('btn-step').addEventListener('click', ()=>{
  if(!step()) {
    document.getElementById('btn-step').disabled=true;
    document.getElementById('btn-run').disabled=true;
    addLog('DFS complete.', 'log-leave');
  }
});
document.getElementById('btn-run').addEventListener('click', ()=>{
  let iterations=0;
  while(dfsStack.length>0 && iterations++<500) step();
  document.getElementById('btn-step').disabled=true;
  document.getElementById('btn-run').disabled=true;
  addLog('DFS complete.', 'log-leave');
  renderSVG(); renderQueries();
});
document.getElementById('btn-reset').addEventListener('click', init);

init();

// ── Startup verification (brute-force cross-check, errors in console) ─────────
(function verify(){
  const par={};
  function dfs(v,p){par[v]=p; for(const c of (CHILDREN[v]||[])) dfs(c,v);}
  dfs(0,null);
  function lcaBrute(u,v){
    const a=new Set(); let x=u;
    while(x!==null){a.add(x);x=par[x];}
    let y=v; while(!a.has(y)) y=par[y]; return y;
  }
  QUERIES_DEF.forEach(([u,v,expected])=>{
    const got=lcaBrute(u,v);
    if(got!==expected) console.error(fmt('LCA(%u%,%v%): expected %expected% got %got%', { u: u, v: v, expected: expected, got: got }));
  });
  console.log('Startup: all LCA expected values verified against brute-force.');
})();

Result

Console

Notice that every query is answered exactly once, at the moment the DFS finishes processing one of the two queried nodes and the other has already been visited (so its ancestor set is tracked by Union-Find). No node is ever revisited. The algorithm is gloriously efficient: the total work is proportional to the size of the tree plus the number of queries — nothing more.

The Real Complexity

Status: solved — Tarjan published the offline LCA algorithm in 1979. It is a provably optimal offline algorithm for the problem.

The algorithm works in three phases:

Preprocessing — Collect all q query pairs and group them by node: for each node u, store the list of queries that involve u.
DFS sweep — Perform a single depth-first traversal of the tree. When the DFS enters node v, create a new Union-Find set for v (its "ancestor set"). When the DFS finishes all children of v and backtracks, merge v's set into its parent's set, making the parent the canonical representative of the merged set. At this moment, any query (u, v) where u has already been fully visited is answered: LCA(u, v) = Find(u) — the current root of u's ancestor set.
Query answers — Each query is answered at most once, in $O(\alpha(n))$ time per Find operation.

Total cost: $O(n)$ for the DFS + $O(q \cdot \alpha(n))$ for all Find calls = $O(n + q \cdot \alpha(n))$ , practically linear.

Why does Find(u) return the correct LCA? Because Union-Find tracks which subtree has been fully processed. When node v finishes, all of v's subtree is merged upward. So Find(u) at that moment returns the deepest ancestor of v that is also an ancestor of u — exactly the LCA.

Compared to alternatives:

Method	Preprocessing	Per query	Total for q queries
Walk up from each node	$O(1)$	$O(n)$	$O(n \cdot q)$
Binary lifting	$O(n \log n)$	$O(\log n)$	$O(n \log n + q \log n)$
Tarjan offline	$O(n)$	$O(\alpha(n))$	$O(n + q \cdot \alpha(n))$
Farach-Colton & Bender (online)	$O(n)$	$O(1)$	$O(n + q)$

The Farach-Colton–Bender algorithm (2000) later achieved true $O(1)$ per query online, but Tarjan's offline approach remains the classic for batch workloads because it is remarkably simple to implement correctly. See also minimum spanning tree for another setting where Union-Find produces an elegant linear bound.

Where It Matters

Answering many ancestor queries at once turns out to be fundamental to a surprising range of fields:

Tree distances in bulk: The identity dist(u, v) = depth(u) + depth(v) − 2·depth(LCA(u,v)) means any batch of distance queries on a weighted tree reduces directly to a batch of LCA queries — Tarjan's algorithm answers all of them in one pass.
Compiler control-flow analysis: Dominators in a control-flow graph — which nodes must be visited before any path to a target — can be computed with LCA queries on a DFS tree. Tarjan used his own algorithm in compiler backends.
Bioinformatics and phylogenetics: Given a phylogenetic tree with thousands of species, biologists routinely need the most recent common ancestor of many pairs. A single offline sweep handles all pairs in linear time.
XML and document processing: Hierarchical documents (HTML, JSON, file systems) support "find nearest common container" queries, which are exactly LCA on the document tree.
Network routing: Shortest paths in tree-structured networks (spanning trees of the internet backbone) rely on fast LCA to find the meeting point of two routes.

Union-Find — the workhorse inside Tarjan's algorithm — appears across algorithms wherever disjoint sets need to be merged and queried efficiently. See also dynamic shortest paths for related tree-manipulation techniques.

Conclusion

Tarjan's offline LCA algorithm distills a powerful idea: batching pays off. Instead of answering each ancestor question the moment it arrives, gather all of them, then sweep the tree once — and let the DFS + Union-Find machinery answer every query at exactly the right instant during the traversal.

The result is near-linear total time regardless of how many queries there are, making it one of the most cost-efficient tricks in classical algorithmics. The algorithm is not merely a theoretical curiosity; it is implemented in competitive programming libraries, compiler toolchains, and bioinformatics pipelines worldwide.

The next time you need to answer thousands of ancestor or distance queries on a tree, remember: collecting them first and sweeping once is almost always faster than handling each one independently.

Comments

Loading comments...

https://www.kipuhub.com/en/article/tarjan-offline-lca/Content licensed under CC BY-NC 4.0.

Cookies & privacy

Tarjan's Offline LCA

Batching tree queries into a single linear sweep