Skip to content

LCA Postorder Review

Naive LCA walks both nodes up to the same depth, then up in lockstep

What We Already Know

Back in Chapter 3, you learned to find the Lowest Common Ancestor of two nodes by walking up the tree. The idea is simple: bring both nodes to the same depth, then walk both up in lockstep until they meet.

This works. It's correct. And for a single query, it's perfectly fine.

The trouble starts when you have \(10^5\) queries.

The Naive Algorithm

Given a rooted tree where each node knows its parent and depth:

  1. If \(depth[u] > depth[v]\), walk \(u\) up until it reaches the same depth as \(v\).
  2. If \(depth[v] > depth[u]\), walk \(v\) up until it reaches the same depth as \(u\).
  3. Now both are at the same depth. Walk both up one step at a time until they meet.

The meeting point is the LCA.

Trace on this tree:

          1
        / | \
       2  3  4
      / \    |
     5   6   7
    /
   8

Depths: \(depth[1]=0, depth[2]=1, depth[3]=1, depth[4]=1, depth[5]=2, depth[6]=2, depth[7]=2, depth[8]=3\).

Query: LCA(8, 6)?

Step \(u\) \(v\) Action
0 8 (depth 3) 6 (depth 2) \(u\) is deeper, walk up
1 5 (depth 2) 6 (depth 2) same depth, walk both
2 2 (depth 1) 2 (depth 1) \(u = v\), done

\(LCA(8, 6) = 2\). Three steps.

Query: LCA(8, 7)?

Step \(u\) \(v\) Action
0 8 (depth 3) 7 (depth 2) \(u\) is deeper, walk up
1 5 (depth 2) 7 (depth 2) same depth, walk both
2 2 (depth 1) 4 (depth 1) different, walk both
3 1 (depth 0) 1 (depth 0) \(u = v\), done

\(LCA(8, 7) = 1\). Four steps.

Query: LCA(3, 3)?

Already the same node. \(LCA = 3\). Zero steps.

The Cost

Each query takes \(O(depth)\) steps in the worst case. On a balanced tree with \(n\) nodes, depth is \(O(\log n)\), so each query is \(O(\log n)\). Not bad.

But trees aren't always balanced. A chain (1 → 2 → 3 → ... → \(n\)) has depth \(n - 1\). A single LCA query could take \(O(n)\) steps.

For \(q\) queries on a tree with \(n\) nodes:

  • Worst case: \(O(nq)\). With \(n = q = 2 \times 10^5\), that's \(4 \times 10^{10}\). Far too slow.
  • Best case (balanced tree): \(O(q \log n)\). Fast enough — but you can't count on the tree being balanced.

The Code

vector<int> adjacency[200005];
int parentOf[200005];
int depthOf[200005];

void dfs(int node, int par, int currentDepth) {
    parentOf[node] = par;
    depthOf[node] = currentDepth;
    for (int child : adjacency[node]) {
        if (child != par) {
            dfs(child, node, currentDepth + 1);
        }
    }
}

int lcaNaive(int u, int v) {
    while (depthOf[u] > depthOf[v]) u = parentOf[u];
    while (depthOf[v] > depthOf[u]) v = parentOf[v];
    while (u != v) {
        u = parentOf[u];
        v = parentOf[v];
    }
    return u;
}

Complexity: \(O(n)\) preprocessing, \(O(n)\) per query worst case.

What We Need

The goal for this chapter: answer \(q\) LCA queries on a tree with \(n\) nodes, where both \(n\) and \(q\) can be up to \(2 \times 10^5\).

Method Preprocessing Per query Total
Naive (this lesson) \(O(n)\) \(O(n)\) \(O(nq)\)
Binary lifting (Lesson 2) \(O(n \log n)\) \(O(\log n)\) \(O(n \log n + q \log n)\)
Euler tour + RMQ (Lesson 3) \(O(n \log n)\) \(O(1)\) \(O(n \log n + q)\)

Both advanced methods spend \(O(n \log n)\) upfront to precompute a table, then answer each query fast. The tradeoff: binary lifting is simpler to code and also gives you \(k\)-th ancestor queries for free. Euler tour + RMQ is faster per query but does nothing beyond LCA.

The naive method isn't useless — it's the right choice when you have exactly one LCA query, or when \(n\) is small enough that \(O(n)\) per query doesn't matter. But for competitive programming constraints, you need one of the next two methods.

Try It

Fill in the lcaNaive function in the starter code.

Predict before running: On the chain 1 → 2 → 3 → 4 → 5, what is \(LCA(5, 3)\)? Node 5 is at depth 4, node 3 is at depth 2. Walk node 5 up twice: 5 → 4 → 3. Now \(u = v = 3\). Answer: 3.

Challenge: What if you're given \(10^5\) queries but the tree is guaranteed to be a complete binary tree with \(n = 2^{17} - 1 \approx 1.3 \times 10^5\) nodes? The depth is at most 16. The naive approach takes at most 32 steps per query. Total: \(3.2 \times 10^6\) — perfectly fine. Know your constraints before over-engineering.

Edge Cases to Watch For

  • One node is a direct ancestor of the other: After equalizing depths, \(u = v\) immediately. If your code skips the "walk up together" phase when \(u = v\) after depth equalization, this works. But if it doesn't check \(u = v\) before the lockstep phase, it walks past the answer.

Problems

Problem Link Difficulty
LC 236 — LCA of a Binary Tree leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree Medium
CSES — Company Queries II cses.fi/problemset/task/1688 Medium