Loading…

hardTreesSometimes asked

Lowest Common Ancestor with Binary Lifting

Q: How do you solve Lowest Common Ancestor with Binary Lifting using the Baseline — Walk Both Pointers Up to the Root approach?

When to use it: Say this first: it is the obvious correct method and it sets the depth/alignment idea that the optimal reuses. The direct method needs only parent pointers and a depth for each node. **Step one — equalize depth.** An LCA cannot be deeper than the shallower of the two nodes. So first lift the deeper node up, one parent at a time, until both nodes sit at the same depth. **Step two — climb in lockstep.** Now move both nodes up one parent at a time together. As long as they differ, keep going; the moment they point at the same node, that node is the LCA. They are guaranteed to meet no later than the root. **Why it is correct.** Once depths are equal, the two upward paths to the root have the same length and converge exactly at the LCA — every node above the LCA is shared, every node below is on a separate branch. **Why it is too slow.** Each phase can traverse the entire height of the tree, which is O(n) for a chain. Answering q queries this way is O(q·n) — fine for a handful of queries, hopeless for 2×10⁵ of them. The fix is to take *big* upward jumps (powers of two) instead of single steps, which is exactly binary lifting. Time complexity: O(n) per query after O(n) depth setup. Space complexity: O(n).

Trees & BST · 23 of 41 · 12 min

You are given a rooted tree with n nodes (the parent of each node, with the root having no parent). Answer up to q queries, each asking for the **lowest common ancestor** of two nodes a and b — the deepest node that is an ancestor of both.

Preprocess once, then answer every query in **O(log n)**.

In plain English

We have one fixed rooted tree and a flood of LCA queries. A single naive walk-up per query is O(n) and too slow in aggregate. Binary lifting precomputes, for every node, its ancestor 1, 2, 4, 8, … steps above. With those jump pointers we can move any node up by an arbitrary amount in O(log n) by combining powers of two, and the LCA reduces to aligning depths and then jumping both nodes as high as possible while they stay on different branches.

Examples

Example 1

Input: tree rooted at 0; edges 0-1,0-2,1-3,1-4,2-5; lca(3, 4)
Output: 1
Note: 3 and 4 are both children of 1, so their lowest common ancestor is 1.

Example 2

Input: same tree; lca(3, 5)
Output: 0
Note: 3 is under 1, 5 is under 2; the only shared ancestor is the root 0.

Example 3

Input: same tree; lca(1, 4)
Output: 1
Note: 1 is itself an ancestor of 4, so the LCA is 1 — the 'one node is an ancestor of the other' case.

Constraints

1 ≤ n ≤ 2 × 10⁵
1 ≤ q ≤ 2 × 10⁵ queries
The tree is rooted and static (does not change between queries)
Nodes are 0-indexed (or 1-indexed); the root has a sentinel parent

Clarifying questions4First question: Is the tree static across queries?Explore questions

Q1.Is the tree static across queries?
Yes. Binary lifting precomputes ancestor tables once; if the tree changed between queries we would need a dynamic structure like link-cut trees instead.
Q2.How many queries relative to n?
Many — that is what justifies O(n log n) preprocessing. For a single query, a plain O(n) walk-up is simpler and just as fast.
Q3.Could the tree be a long chain (degenerate)?
Yes, depth can reach n. The DFS that fills depths should be iterative (explicit stack) so a chain of 2×10⁵ nodes does not overflow the recursion stack.
Q4.Do we also need distance or k-th ancestor?
If so, the same up table answers them: k-th ancestor by decomposing k into set bits, and distance(u,v) = depth[u] + depth[v] − 2·depth[lca(u,v)].

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

To answer many LCA queries on a fixed rooted tree, precompute `up[node][j]` = the 2^j-th ancestor of node, for j up to log n. Build it with one DFS for depths plus the recurrence `up[v][j] = up[ up[v][j-1] ][j-1]`. To answer LCA(a, b): lift the deeper node up to the other's depth, then lift both in powers of two while their ancestors differ. Preprocessing is O(n log n); each query is O(log n).

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you can design O(n log n) preprocessing that makes each query O(log n), and whether you correctly handle the two-phase query: equalize depths, then lift both nodes while ancestors differ.

Where candidates slip

Returning the node where the lifts meet instead of its parent, forgetting the already-an-ancestor case (one node is the LCA), or sizing the up table with too few levels so a deep jump runs off the end.

How to stand out

Derive LOG from n, explain the doubling recurrence in one line, and note that distance and k-th ancestor reuse the same table. Mention the iterative DFS to avoid stack overflow on a tree that is a long chain.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Baseline — Walk Both Pointers Up to the Root	`O(n) per query after O(n) depth setup`	`O(n)`	Say this first: it is the obvious correct method and it sets the depth/alignment idea that the optimal reuses.	Read
2	Binary Lifting — Sparse Ancestor Table (Optimal)Optimal	`O(n log n) preprocess, O(log n) per query`	`O(n log n)`	The answer they want for many queries. 'Precompute the 2^j-th ancestor of every node, then jump in powers of two.'	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.Explore the full tree

Example tree rooted at 0

How to read it:lca(3,4)=1 (siblings' parent); lca(3,5)=0 (different branches meet at the root).

Rendering diagram…

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Baseline — Walk Both Pointers Up to the Root

TimeO(n) per query after O(n) depth setupSpaceO(n)

Say this first: it is the obvious correct method and it sets the depth/alignment idea that the optimal reuses.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

First make both nodes the same depth: lift the deeper one parent-by-parent until depths match.

2Hint 2Explore hint

Then move both up one step at a time in lockstep; the first node where they coincide is the LCA.

3Hint 3Explore hint

Each query can walk the whole height of the tree — O(n) per query. With many queries that is too slow, which motivates jump pointers.

A · Core idea

The direct method needs only parent pointers and a depth for each node.

Step one — equalize depth. An LCA cannot be deeper than the shallower of the two nodes. So first lift the deeper node up, one parent at a time, until both nodes sit at the same depth.

Step two — climb in lockstep. Now move both nodes up one parent at a time together. As long as they differ, keep going; the moment they point at the same node, that node is the LCA. They are guaranteed to meet no later than the root.

Why it is correct. Once depths are equal, the two upward paths to the root have the same length and converge exactly at the LCA — every node above the LCA is shared, every node below is on a separate branch.

Why it is too slow. Each phase can traverse the entire height of the tree, which is O(n) for a chain. Answering q queries this way is O(q·n) — fine for a handful of queries, hopeless for 2×10⁵ of them. The fix is to take big upward jumps (powers of two) instead of single steps, which is exactly binary lifting.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

tree rooted at 0: 0-1,0-2,1-3,1-4,2-5; lca(3, 5)

depths

depth[3]=2, depth[5]=2 — already equal

Statea=3, b=5

Final result0

C · Code with teaching comments

Reference implementation previewimport java.util.*; class NaiveLCA { private final List<List<Integer>> adj; private final int[] parent, depth;Explore the full code

solution.javaJava

Baseline — Walk Both Pointers Up to the Root — reference

3 teaching notes

1
import java.util.*;
2
 
3
class NaiveLCA {
4
    private final List<List<Integer>> adj;
5
    private final int[] parent, depth;
6
 
7
    NaiveLCA(int n, int root, int[][] edges) {
8
        adj = new ArrayList<>();
9
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
10
        for (int[] e : edges) { adj.get(e[0]).add(e[1]); adj.get(e[1]).add(e[0]); }
11
        parent = new int[n];
12
        depth = new int[n];
13
        // Iterative DFS to avoid stack overflow on deep/chain trees.
14
        Deque<int[]> stack = new ArrayDeque<>();
15
        // Iterative DFS so a chain of 2×10⁵ nodes does not overflow the recursion
16
        // stack.
17
        stack.push(new int[]{root, root, 0});  // node, par, dep
18
        boolean[] seen = new boolean[n];
19
        while (!stack.isEmpty()) {
20
            int[] cur = stack.pop();
21
            int node = cur[0], par = cur[1], dep = cur[2];
22
            if (seen[node]) continue;
23
            seen[node] = true;
24
            parent[node] = par;
25
            depth[node] = dep;
26
            for (int next : adj.get(node)) {
27
                if (!seen[next]) stack.push(new int[]{next, node, dep + 1});
28
            }
29
        }
30
    }
31
 
32
    int lca(int a, int b) {
33
        // Equalize depth by lifting the deeper node one parent at a time.
34
        while (depth[a] > depth[b]) a = parent[a];
35
        while (depth[b] > depth[a]) b = parent[b];
36
        // Lockstep climb; the meeting point is the LCA. This loop is the O(n)
37
        // bottleneck.
38
        while (a != b) { a = parent[a]; b = parent[b]; }
39
        return a;
40
    }
41
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.41 lines

D · Why it works and complexityO(n) per query after O(n) depth setup timeO(n) spaceOpen the invariant and proofExplore the proof

The two-phase structure — equalize depth, then climb together — is identical in the optimal solution. Binary lifting changes only how you climb: instead of one step at a time, you take the largest power-of-two jump that does not overshoot, cutting O(n) climbing to O(log n).

ComplexityO(n) per query after O(n) depth setup time, O(n) space — Equalizing depths is up to O(n) parent steps, and the lockstep walk is up to O(n) more. With q queries this is O(q·n) in the worst case (e.g. a chain).

E · Edge cases and pitfalls3Recursive DFS on a chain of 2×10⁵ nodes — stack overflow; use an explicit stack.Explore edge cases

Pitfalls

Recursive DFS on a chain of 2×10⁵ nodes — stack overflow; use an explicit stack.
Climbing before equalizing depths — the pointers can pass each other and never meet.
Accepting O(n) per query — fine for one query, far too slow for many.

03.2

Approach 2 of 2 · Optimal

Binary Lifting — Sparse Ancestor Table (Optimal)

TimeO(n log n) preprocess, O(log n) per querySpaceO(n log n)

The answer they want for many queries. 'Precompute the 2^j-th ancestor of every node, then jump in powers of two.'

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Store up[v][j] = the ancestor of v that is 2^j steps above it. up[v][0] is just the parent.

2Hint 2Explore hint

Fill the table by doubling: a 2^j jump is two 2^(j-1) jumps, so up[v][j] = up[ up[v][j-1] ][j-1]. Compute level by level.

3Hint 3Explore hint

Query in two phases: lift the deeper node by the depth gap (decomposed into powers of two), then for j from high to low, jump BOTH nodes up by 2^j whenever their ancestors there differ. The LCA is the parent of where they stop.

A · Core idea

Binary lifting precomputes jump pointers so any upward movement becomes a handful of power-of-two hops.

The table. Define up[v][j] as the ancestor reached by climbing 2^j parents from v. The base level is the parent: up[v][0] = parent[v]. The doubling recurrence builds the rest: climbing 2^j steps is the same as climbing 2^(j-1) steps and then 2^(j-1) steps again, so up[v][j] = up[ up[v][j-1] ][j-1]. Because each higher level depends only on the level below, fill the table column by column (all j-1 before any j). With LOG = ⌈log₂ n⌉ + 1 columns, the deepest possible jump is covered.

Jumping by an arbitrary amount. To climb exactly k steps, write k in binary and take one jump per set bit: for each bit j set in k, replace v with up[v][j]. Since k < n has at most log₂ n set bits, this is O(log n).

Query phase 1 — equalize depth. Suppose depth[a] ≥ depth[b]. Lift a up by depth[a] − depth[b] using the bit decomposition above, so both nodes sit at the same depth. If a == b now, one node was an ancestor of the other and that node is the LCA — return it immediately. Missing this check is a classic bug.

Query phase 2 — rise to just below the LCA. Now both nodes are at equal depth but on (possibly) different branches. For j from the highest level down to 0, look at up[a][j] and up[b][j]: if they are different, jump both up by 2^j (their ancestors still differ, so the LCA is higher). If they are the same, that jump would overshoot — skip it. After the loop, a and b sit on different branches but their parents coincide: the LCA is up[a][0].

Why scanning j from high to low works. It is a binary search on the climb distance. Greedily taking the biggest jump that keeps the two nodes distinct lands them exactly one step below the LCA — every set bit of the true distance gets taken once, none overshoots. The sentinel parent at the root makes 'jump past the root' return the root, so out-of-range jumps are harmless.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

tree rooted at 0: 0-1,0-2,1-3,1-4,2-5; lca(3, 5). depths: 3→2, 5→2.

Interactive diagram

Two-phase query for lca(3,5)

build up[][0]

Active call / nodeSupporting contextReturned stateNot active

Depths already equal; the high-to-low scan keeps both nodes on different branches, stopping at 1 and 2 whose shared parent 0 is the LCA.

Final result0

C · Code with teaching comments

solution.javaJava

Binary Lifting — Sparse Ancestor Table (Optimal) — optimal

7 teaching notes

1
import java.util.*;
2
 
3
class BinaryLiftingLCA {
4
    private final int LOG;
5
    private final int[][] up;   // up[v][j] = 2^j-th ancestor of v
6
    private final int[] depth;
7
    private final List<List<Integer>> adj;
8
 
9
    BinaryLiftingLCA(int n, int root, int[][] edges) {
10
        // Number of columns = ⌈log2 n⌉ + 1 (at least 1), enough for the deepest jump.
11
        LOG = Math.max(1, 32 - Integer.numberOfLeadingZeros(n));
12
        up = new int[n][LOG];
13
        depth = new int[n];
14
        adj = new ArrayList<>();
15
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
16
        for (int[] e : edges) { adj.get(e[0]).add(e[1]); adj.get(e[1]).add(e[0]); }
17
 
18
        // Iterative DFS: set depth and up[v][0] = parent (root's parent = root).
19
        Deque<int[]> stack = new ArrayDeque<>();
20
        boolean[] seen = new boolean[n];
21
        stack.push(new int[]{root, root, 0});
22
        while (!stack.isEmpty()) {
23
            int[] cur = stack.pop();
24
            int node = cur[0], par = cur[1], dep = cur[2];
25
            if (seen[node]) continue;
26
            seen[node] = true;
27
            // Base level is the direct parent; the root's parent is itself (sentinel).
28
            up[node][0] = par;
29
            depth[node] = dep;
30
            for (int next : adj.get(node)) {
31
                if (!seen[next]) stack.push(new int[]{next, node, dep + 1});
32
            }
33
        }
34
        // Doubling: up[v][j] = up[ up[v][j-1] ][j-1].
35
        for (int j = 1; j < LOG; j++) {
36
            for (int v = 0; v < n; v++) {
37
                // Doubling: a 2^j jump is two 2^(j-1) jumps chained.
38
                up[v][j] = up[ up[v][j - 1] ][j - 1];
39
            }
40
        }
41
    }
42
 
43
    int lca(int a, int b) {
44
        if (depth[a] < depth[b]) { int t = a; a = b; b = t; }
45
        int diff = depth[a] - depth[b];
46
        for (int j = 0; j < LOG; j++) {        // lift a to b's depth
47
            // Lift the deeper node by the depth gap, one set bit at a time.
48
            if (((diff >> j) & 1) == 1) a = up[a][j];
49
        }
50
        if (a == b) return a;                  // b was an ancestor of a
51
        for (int j = LOG - 1; j >= 0; j--) {   // rise while ancestors differ
52
            // Jump both up only while their ancestors differ; stop just below the LCA.
53
            if (up[a][j] != up[b][j]) { a = up[a][j]; b = up[b][j]; }
54
        }
55
        // The nodes are one step below the LCA, so its parent is the answer.
56
        return up[a][0];
57
    }
58
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.58 lines

D · Why it works and complexityO(n log n) preprocess, O(log n) per query timeO(n log n) spaceOpen the invariant and proofExplore the proof

Binary lifting is the doubling trick applied to the parent function: precompute f^(2^j) so you can apply f any number of times in O(log n). The LCA query is then a depth alignment followed by a binary search for the highest divergence point. The exact same table answers k-th-ancestor and, via depths, path distance — one preprocessing, many queries.

ComplexityO(n log n) preprocess, O(log n) per query time, O(n log n) space — The table has n rows and log n columns, each filled in O(1) → O(n log n) build. A query does at most log n jumps to equalize depth plus log n jumps in the second phase → O(log n) per query. Space is the table, O(n log n).

E · Edge cases and pitfalls7lca(node, node) — Depths equal, a == b after phase 1 → returns the node itself.Explore edge cases

Edge cases handled

lca(node, node)Depths equal, a == b after phase 1 → returns the node itself.
One node is an ancestor of the otherAfter equalizing depth the deeper node lifts onto the shallower one; the a == b check returns it as the LCA.
Jump past the rootThe root's sentinel parent (itself) makes over-long jumps stay at the root, so up[][j] never indexes out of range.

Pitfalls

Returning the meeting node from phase 2 instead of its parent (up[a][0]).
Skipping the a == b check after depth alignment — wrong on the ancestor case.
Too few columns (LOG) so a deep jump runs off the table.
Recursive DFS for the depth/parent setup — stack overflow on a chain; use an explicit stack.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewimport java.util.*; class BinaryLiftingLCA { private final int LOG; private final int[][] up; // up[v][j] = 2^j-th ancestor of vExplore the playground

Try it — Java· run a complete program; method snippets need a driver

import java.util.*;

class BinaryLiftingLCA {
    private final int LOG;
    private final int[][] up;   // up[v][j] = 2^j-th ancestor of v
    private final int[] depth;
    private final List<List<Integer>> adj;

BinaryLiftingLCA(int n, int root, int[][] edges) {
        LOG = Math.max(1, 32 - Integer.numberOfLeadingZeros(n));
        up = new int[n][LOG];
        depth = new int[n];
        adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        for (int[] e : edges) { adj.get(e[0]).add(e[1]); adj.get(e[1]).add(e[0]); }

// Iterative DFS: set depth and up[v][0] = parent (root's parent = root).
        Deque<int[]> stack = new ArrayDeque<>();
        boolean[] seen = new boolean[n];
        stack.push(new int[]{root, root, 0});
        while (!stack.isEmpty()) {
            int[] cur = stack.pop();
            int node = cur[0], par = cur[1], dep = cur[2];
            if (seen[node]) continue;
            seen[node] = true;
            up[node][0] = par;
            depth[node] = dep;
            for (int next : adj.get(node)) {
                if (!seen[next]) stack.push(new int[]{next, node, dep + 1});
            }
        }
        // Doubling: up[v][j] = up[ up[v][j-1] ][j-1].
        for (int j = 1; j < LOG; j++) {
            for (int v = 0; v < n; v++) {
                up[v][j] = up[ up[v][j - 1] ][j - 1];
            }
        }
    }

int lca(int a, int b) {
        if (depth[a] < depth[b]) { int t = a; a = b; b = t; }
        int diff = depth[a] - depth[b];
        for (int j = 0; j < LOG; j++) {        // lift a to b's depth
            if (((diff >> j) & 1) == 1) a = up[a][j];
        }
        if (a == b) return a;                  // b was an ancestor of a
        for (int j = LOG - 1; j >= 0; j--) {   // rise while ancestors differ
            if (up[a][j] != up[b][j]) { a = up[a][j]; b = up[b][j]; }
        }
        return up[a][0];
    }
}

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Returning the stop node, not its parent

Phase 2 deliberately stops one level BELOW the LCA (where the two nodes are still on different branches). The answer is their common parent, up[a][0] — returning a itself gives a wrong, too-deep node.

Explore the code comparison

Don't write this

for j in range(self.LOG - 1, -1, -1):
    if self.up[a][j] != self.up[b][j]:
        a = self.up[a][j]; b = self.up[b][j]
return a            # wrong: a is one level below the LCA

Write this instead

for j in range(self.LOG - 1, -1, -1):
    if self.up[a][j] != self.up[b][j]:
        a = self.up[a][j]; b = self.up[b][j]
return self.up[a][0]   # the shared parent is the LCA

Missing the ancestor case

If b is an ancestor of a, then after lifting a to b's depth we get a == b. Without an early return, phase 2's loop never moves (ancestors are already equal at every level) and you return up[a][0] = the parent of b, which is wrong.

Explore the code comparison

Don't write this

int diff = depth[a] - depth[b];
for (int j = 0; j < LOG; j++) if (((diff>>j)&1)==1) a = up[a][j];
// missing: if (a == b) return a;
for (int j = LOG-1; j>=0; j--) { ... }
return up[a][0];   // returns parent of the true LCA

Write this instead

int diff = depth[a] - depth[b];
for (int j = 0; j < LOG; j++) if (((diff>>j)&1)==1) a = up[a][j];
if (a == b) return a;   // one node was an ancestor of the other
for (int j = LOG-1; j>=0; j--) { ... }
return up[a][0];

Too few ancestor levels

If LOG is smaller than ⌈log2 n⌉ + 1, the largest jump cannot reach the root from the deepest node, so depth alignment and the rise loop both miss high ancestors.

Explore the code comparison

Don't write this

self.LOG = 16        # hard-coded; breaks when n needs more bits

Write this instead

self.LOG = max(1, n.bit_length())   # scales with n

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Sparse ancestor table — jump in powers of two using up[v][j] = up[up[v][j-1]][j-1]

Code pattern to memorize

up[v][0] = parent[v]
up[v][j] = up[ up[v][j-1] ][j-1]
lca(a, b):
  level a, b to equal depth, then
  for j in high..0: if up[a][j] != up[b][j]: a, b = up[a][j], up[b][j]
  return up[a][0]

Rules to remember

1up[v][0] is the direct parent; the root's parent is a sentinel (itself or 0/-1) so lifts past the root stay safe.
2Allocate LOG = ceil(log2(n)) + 1 levels — enough to cover the deepest possible jump.
3Equalize depths first: lift the deeper node by the depth difference, decomposed into powers of two.
4Then lift both nodes by the largest jump that keeps their ancestors different; the answer is the parent of where they stop.
5If after equalizing the nodes are already equal, that node is the LCA — handle it before the binary search.

Use this pattern when

Many LCA queries on a static rooted tree (the tree does not change between queries)
k-th ancestor queries, or distance(u, v) = depth[u] + depth[v] − 2·depth[lca]
Jump-pointer problems: 'follow parent 2^j times' on any functional graph
Path queries on trees that reduce to ancestor lookups

Choose another pattern when

Tree changes between queries (links added/removed) → use link-cut trees or Euler-tour + segment tree
Only one or two LCA queries → a single O(n) walk-up is simpler than O(n log n) preprocessing
It is actually a BST → LCA is a single O(h) descent comparing values, no lifting needed
You need LCA on a DAG, not a tree → binary lifting assumes a unique parent per node

Interview takeaway

Binary lifting turns 'walk up k steps' from O(k) into O(log k) by precomputing power-of-two jumps — the same doubling trick behind fast exponentiation and sparse tables. LCA falls out by aligning depths and then binary-searching the highest point where the two paths still diverge.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternBinary lifting: precompute up[v][j] = the 2^j-th ancestor via the doubling recurrence up[v][j] = up[up[v][j-1]][j-1]. Answer LCA by equalizing depth then binary-searching the highest divergence point — O(n log n) build, O(log n) query. The same table powers k-th ancestor and path-distance queries on static rooted trees.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Lowest Common Ancestor of a Binary Tree
For a single query on a general binary tree, a one-pass recursion is simpler than building lifting tables.
Kth Ancestor of a Tree Node
Coming soon
Exactly the up[][] table — decompose k into set bits and take one jump per bit.
Distance Between Two Nodes
Coming soon
depth[u] + depth[v] − 2·depth[lca(u, v)] reuses the same preprocessing.
Euler Tour of a Tree
An alternative LCA route: Euler tour + range-minimum on depths answers LCA in O(1) after O(n log n) build.

Same pattern

←

Symmetric Tree

Continue · Next problem

Centroid of a Tree

hardTreesSometimes asked

Lowest Common Ancestor with Binary Lifting

Trees & BST · 23 of 41 · 12 min

Preprocess once, then answer every query in **O(log n)**.

In plain English

Examples

Example 1

Input: tree rooted at 0; edges 0-1,0-2,1-3,1-4,2-5; lca(3, 4)
Output: 1
Note: 3 and 4 are both children of 1, so their lowest common ancestor is 1.

Example 2

Input: same tree; lca(3, 5)
Output: 0
Note: 3 is under 1, 5 is under 2; the only shared ancestor is the root 0.

Example 3

Input: same tree; lca(1, 4)
Output: 1
Note: 1 is itself an ancestor of 4, so the LCA is 1 — the 'one node is an ancestor of the other' case.

Constraints

1 ≤ n ≤ 2 × 10⁵
1 ≤ q ≤ 2 × 10⁵ queries
The tree is rooted and static (does not change between queries)
Nodes are 0-indexed (or 1-indexed); the root has a sentinel parent

Clarifying questions4First question: Is the tree static across queries?Explore questions

Q1.Is the tree static across queries?
Yes. Binary lifting precomputes ancestor tables once; if the tree changed between queries we would need a dynamic structure like link-cut trees instead.
Q2.How many queries relative to n?
Many — that is what justifies O(n log n) preprocessing. For a single query, a plain O(n) walk-up is simpler and just as fast.
Q3.Could the tree be a long chain (degenerate)?
Yes, depth can reach n. The DFS that fills depths should be iterative (explicit stack) so a chain of 2×10⁵ nodes does not overflow the recursion stack.
Q4.Do we also need distance or k-th ancestor?
If so, the same up table answers them: k-th ancestor by decomposing k into set bits, and distance(u,v) = depth[u] + depth[v] − 2·depth[lca(u,v)].

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you can design O(n log n) preprocessing that makes each query O(log n), and whether you correctly handle the two-phase query: equalize depths, then lift both nodes while ancestors differ.

Where candidates slip

How to stand out

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Baseline — Walk Both Pointers Up to the Root	`O(n) per query after O(n) depth setup`	`O(n)`	Say this first: it is the obvious correct method and it sets the depth/alignment idea that the optimal reuses.	Read
2	Binary Lifting — Sparse Ancestor Table (Optimal)Optimal	`O(n log n) preprocess, O(log n) per query`	`O(n log n)`	The answer they want for many queries. 'Precompute the 2^j-th ancestor of every node, then jump in powers of two.'	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.Explore the full tree

Example tree rooted at 0

How to read it:lca(3,4)=1 (siblings' parent); lca(3,5)=0 (different branches meet at the root).

Rendering diagram…

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Baseline — Walk Both Pointers Up to the Root

TimeO(n) per query after O(n) depth setupSpaceO(n)

Say this first: it is the obvious correct method and it sets the depth/alignment idea that the optimal reuses.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

First make both nodes the same depth: lift the deeper one parent-by-parent until depths match.

2Hint 2Explore hint

Then move both up one step at a time in lockstep; the first node where they coincide is the LCA.

3Hint 3Explore hint

Each query can walk the whole height of the tree — O(n) per query. With many queries that is too slow, which motivates jump pointers.

A · Core idea

The direct method needs only parent pointers and a depth for each node.

Step one — equalize depth. An LCA cannot be deeper than the shallower of the two nodes. So first lift the deeper node up, one parent at a time, until both nodes sit at the same depth.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

tree rooted at 0: 0-1,0-2,1-3,1-4,2-5; lca(3, 5)

depths

depth[3]=2, depth[5]=2 — already equal

Statea=3, b=5

Final result0

C · Code with teaching comments

Reference implementation previewimport java.util.*; class NaiveLCA { private final List<List<Integer>> adj; private final int[] parent, depth;Explore the full code

solution.javaJava

Baseline — Walk Both Pointers Up to the Root — reference

3 teaching notes

1
import java.util.*;
2
 
3
class NaiveLCA {
4
    private final List<List<Integer>> adj;
5
    private final int[] parent, depth;
6
 
7
    NaiveLCA(int n, int root, int[][] edges) {
8
        adj = new ArrayList<>();
9
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
10
        for (int[] e : edges) { adj.get(e[0]).add(e[1]); adj.get(e[1]).add(e[0]); }
11
        parent = new int[n];
12
        depth = new int[n];
13
        // Iterative DFS to avoid stack overflow on deep/chain trees.
14
        Deque<int[]> stack = new ArrayDeque<>();
15
        // Iterative DFS so a chain of 2×10⁵ nodes does not overflow the recursion
16
        // stack.
17
        stack.push(new int[]{root, root, 0});  // node, par, dep
18
        boolean[] seen = new boolean[n];
19
        while (!stack.isEmpty()) {
20
            int[] cur = stack.pop();
21
            int node = cur[0], par = cur[1], dep = cur[2];
22
            if (seen[node]) continue;
23
            seen[node] = true;
24
            parent[node] = par;
25
            depth[node] = dep;
26
            for (int next : adj.get(node)) {
27
                if (!seen[next]) stack.push(new int[]{next, node, dep + 1});
28
            }
29
        }
30
    }
31
 
32
    int lca(int a, int b) {
33
        // Equalize depth by lifting the deeper node one parent at a time.
34
        while (depth[a] > depth[b]) a = parent[a];
35
        while (depth[b] > depth[a]) b = parent[b];
36
        // Lockstep climb; the meeting point is the LCA. This loop is the O(n)
37
        // bottleneck.
38
        while (a != b) { a = parent[a]; b = parent[b]; }
39
        return a;
40
    }
41
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.41 lines

D · Why it works and complexityO(n) per query after O(n) depth setup timeO(n) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls3Recursive DFS on a chain of 2×10⁵ nodes — stack overflow; use an explicit stack.Explore edge cases

Pitfalls

Recursive DFS on a chain of 2×10⁵ nodes — stack overflow; use an explicit stack.
Climbing before equalizing depths — the pointers can pass each other and never meet.
Accepting O(n) per query — fine for one query, far too slow for many.

03.2

Approach 2 of 2 · Optimal

Binary Lifting — Sparse Ancestor Table (Optimal)

TimeO(n log n) preprocess, O(log n) per querySpaceO(n log n)

The answer they want for many queries. 'Precompute the 2^j-th ancestor of every node, then jump in powers of two.'

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Store up[v][j] = the ancestor of v that is 2^j steps above it. up[v][0] is just the parent.

2Hint 2Explore hint

Fill the table by doubling: a 2^j jump is two 2^(j-1) jumps, so up[v][j] = up[ up[v][j-1] ][j-1]. Compute level by level.

3Hint 3Explore hint

A · Core idea

Binary lifting precomputes jump pointers so any upward movement becomes a handful of power-of-two hops.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

tree rooted at 0: 0-1,0-2,1-3,1-4,2-5; lca(3, 5). depths: 3→2, 5→2.

Interactive diagram

Two-phase query for lca(3,5)

build up[][0]

Active call / nodeSupporting contextReturned stateNot active

Depths already equal; the high-to-low scan keeps both nodes on different branches, stopping at 1 and 2 whose shared parent 0 is the LCA.

Final result0

C · Code with teaching comments

solution.javaJava

Binary Lifting — Sparse Ancestor Table (Optimal) — optimal

7 teaching notes

1
import java.util.*;
2
 
3
class BinaryLiftingLCA {
4
    private final int LOG;
5
    private final int[][] up;   // up[v][j] = 2^j-th ancestor of v
6
    private final int[] depth;
7
    private final List<List<Integer>> adj;
8
 
9
    BinaryLiftingLCA(int n, int root, int[][] edges) {
10
        // Number of columns = ⌈log2 n⌉ + 1 (at least 1), enough for the deepest jump.
11
        LOG = Math.max(1, 32 - Integer.numberOfLeadingZeros(n));
12
        up = new int[n][LOG];
13
        depth = new int[n];
14
        adj = new ArrayList<>();
15
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
16
        for (int[] e : edges) { adj.get(e[0]).add(e[1]); adj.get(e[1]).add(e[0]); }
17
 
18
        // Iterative DFS: set depth and up[v][0] = parent (root's parent = root).
19
        Deque<int[]> stack = new ArrayDeque<>();
20
        boolean[] seen = new boolean[n];
21
        stack.push(new int[]{root, root, 0});
22
        while (!stack.isEmpty()) {
23
            int[] cur = stack.pop();
24
            int node = cur[0], par = cur[1], dep = cur[2];
25
            if (seen[node]) continue;
26
            seen[node] = true;
27
            // Base level is the direct parent; the root's parent is itself (sentinel).
28
            up[node][0] = par;
29
            depth[node] = dep;
30
            for (int next : adj.get(node)) {
31
                if (!seen[next]) stack.push(new int[]{next, node, dep + 1});
32
            }
33
        }
34
        // Doubling: up[v][j] = up[ up[v][j-1] ][j-1].
35
        for (int j = 1; j < LOG; j++) {
36
            for (int v = 0; v < n; v++) {
37
                // Doubling: a 2^j jump is two 2^(j-1) jumps chained.
38
                up[v][j] = up[ up[v][j - 1] ][j - 1];
39
            }
40
        }
41
    }
42
 
43
    int lca(int a, int b) {
44
        if (depth[a] < depth[b]) { int t = a; a = b; b = t; }
45
        int diff = depth[a] - depth[b];
46
        for (int j = 0; j < LOG; j++) {        // lift a to b's depth
47
            // Lift the deeper node by the depth gap, one set bit at a time.
48
            if (((diff >> j) & 1) == 1) a = up[a][j];
49
        }
50
        if (a == b) return a;                  // b was an ancestor of a
51
        for (int j = LOG - 1; j >= 0; j--) {   // rise while ancestors differ
52
            // Jump both up only while their ancestors differ; stop just below the LCA.
53
            if (up[a][j] != up[b][j]) { a = up[a][j]; b = up[b][j]; }
54
        }
55
        // The nodes are one step below the LCA, so its parent is the answer.
56
        return up[a][0];
57
    }
58
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.58 lines

D · Why it works and complexityO(n log n) preprocess, O(log n) per query timeO(n log n) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls7lca(node, node) — Depths equal, a == b after phase 1 → returns the node itself.Explore edge cases

Edge cases handled

lca(node, node)Depths equal, a == b after phase 1 → returns the node itself.
One node is an ancestor of the otherAfter equalizing depth the deeper node lifts onto the shallower one; the a == b check returns it as the LCA.
Jump past the rootThe root's sentinel parent (itself) makes over-long jumps stay at the root, so up[][j] never indexes out of range.

Pitfalls

Returning the meeting node from phase 2 instead of its parent (up[a][0]).
Skipping the a == b check after depth alignment — wrong on the ancestor case.
Too few columns (LOG) so a deep jump runs off the table.
Recursive DFS for the depth/parent setup — stack overflow on a chain; use an explicit stack.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewimport java.util.*; class BinaryLiftingLCA { private final int LOG; private final int[][] up; // up[v][j] = 2^j-th ancestor of vExplore the playground

Try it — Java· run a complete program; method snippets need a driver

import java.util.*;

class BinaryLiftingLCA {
    private final int LOG;
    private final int[][] up;   // up[v][j] = 2^j-th ancestor of v
    private final int[] depth;
    private final List<List<Integer>> adj;

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Returning the stop node, not its parent

Explore the code comparison

Don't write this

for j in range(self.LOG - 1, -1, -1):
    if self.up[a][j] != self.up[b][j]:
        a = self.up[a][j]; b = self.up[b][j]
return a            # wrong: a is one level below the LCA

Write this instead

for j in range(self.LOG - 1, -1, -1):
    if self.up[a][j] != self.up[b][j]:
        a = self.up[a][j]; b = self.up[b][j]
return self.up[a][0]   # the shared parent is the LCA

Missing the ancestor case

Explore the code comparison

Don't write this

int diff = depth[a] - depth[b];
for (int j = 0; j < LOG; j++) if (((diff>>j)&1)==1) a = up[a][j];
// missing: if (a == b) return a;
for (int j = LOG-1; j>=0; j--) { ... }
return up[a][0];   // returns parent of the true LCA

Write this instead

int diff = depth[a] - depth[b];
for (int j = 0; j < LOG; j++) if (((diff>>j)&1)==1) a = up[a][j];
if (a == b) return a;   // one node was an ancestor of the other
for (int j = LOG-1; j>=0; j--) { ... }
return up[a][0];

Too few ancestor levels

If LOG is smaller than ⌈log2 n⌉ + 1, the largest jump cannot reach the root from the deepest node, so depth alignment and the rise loop both miss high ancestors.

Explore the code comparison

Don't write this

self.LOG = 16        # hard-coded; breaks when n needs more bits

Write this instead

self.LOG = max(1, n.bit_length())   # scales with n

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Sparse ancestor table — jump in powers of two using up[v][j] = up[up[v][j-1]][j-1]

Code pattern to memorize

up[v][0] = parent[v]
up[v][j] = up[ up[v][j-1] ][j-1]
lca(a, b):
  level a, b to equal depth, then
  for j in high..0: if up[a][j] != up[b][j]: a, b = up[a][j], up[b][j]
  return up[a][0]

Rules to remember

1up[v][0] is the direct parent; the root's parent is a sentinel (itself or 0/-1) so lifts past the root stay safe.
2Allocate LOG = ceil(log2(n)) + 1 levels — enough to cover the deepest possible jump.
3Equalize depths first: lift the deeper node by the depth difference, decomposed into powers of two.
4Then lift both nodes by the largest jump that keeps their ancestors different; the answer is the parent of where they stop.
5If after equalizing the nodes are already equal, that node is the LCA — handle it before the binary search.

Use this pattern when

Many LCA queries on a static rooted tree (the tree does not change between queries)
k-th ancestor queries, or distance(u, v) = depth[u] + depth[v] − 2·depth[lca]
Jump-pointer problems: 'follow parent 2^j times' on any functional graph
Path queries on trees that reduce to ancestor lookups

Choose another pattern when

Tree changes between queries (links added/removed) → use link-cut trees or Euler-tour + segment tree
Only one or two LCA queries → a single O(n) walk-up is simpler than O(n log n) preprocessing
It is actually a BST → LCA is a single O(h) descent comparing values, no lifting needed
You need LCA on a DAG, not a tree → binary lifting assumes a unique parent per node

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Lowest Common Ancestor of a Binary Tree
For a single query on a general binary tree, a one-pass recursion is simpler than building lifting tables.
Kth Ancestor of a Tree Node
Coming soon
Exactly the up[][] table — decompose k into set bits and take one jump per bit.
Distance Between Two Nodes
Coming soon
depth[u] + depth[v] − 2·depth[lca(u, v)] reuses the same preprocessing.
Euler Tour of a Tree
An alternative LCA route: Euler tour + range-minimum on depths answers LCA in O(1) after O(n log n) build.

Same pattern

←

Symmetric Tree

Continue · Next problem

Centroid of a Tree