Least Common Ancestor (LCA)
Post
Cancel

# Where is this useful?

The Least Common Ancestor (LCA) data structure is useful wherever you have a directed graph where every vertex has out-degree $$\leq 1$$. In more common terms, each vertex has a unique determined ‘parent’, or it is a root node, with no parent. The most common (and almost always only) example being a rooted tree.

On these particular graphs, the LCA gives us a fast way to move ‘up’ the graph (Towards your parents). In particular, we can use this to find the least common ancestor in $$\log (N)$$ time, where the data structure gets its name from.

Reusing the analogy of parenting vertices, a vertex $$u$$ is an ancestor of $$v$$ if $$u$$ is $$v$$’s parent, or $$v$$’s parent’s parent, and so on. As long as there is a line of ‘parentage’ connecting $$v$$ to $$u$$, $$u$$ is an ancestor of $$v$$. We consider $$v$$ to also be it’s own ancestor.

The least common ancestor problem then requires, given two vertices $$x$$ and $$y$$, to find a vertex $$z$$ in the graph such that $$z$$ is an ancestor of both $$x$$ and $$y$$, but there is no vertex $$z’ \neq z$$ such that $$z$$ is an ancestor of $$z’$$ and $$z’$$ is an ancestor of $$x$$ and $$y$$ (In the tree example, we just want to find the lowest depth vertex whose subtree contains boths $$x$$ and $$y$$).

Note that the least common ancestor can be $$x$$ or $$y$$, if $$x$$ is an ancestor of $$y$$ or vice-versa.

# Implementing the Data Structure

## Interface

Let’s start by defining an interface for this data structure, and then slowly implement our methods.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 class LCA: """ vertices are represented as numbers 0->n-1. """ def __init__(self, n_vertices): self.n = n_vertices self.adjacent = [[] for _ in range(self.n)] def add_edge(self, u, v, weight=1): self.adjacent[u].append((v, weight)) self.adjacent[v].append((u, weight)) def build(self, root): # Once edges are added, build the tree/data structure. pass # TODO def query(self, u, v, root=None): # What is the lowest common ancestor of u, v? # Extension: Make this query from any root vertex you want. pass # TODO def dist(self, u, v): # Find the distance between two vertices - very simple if we have LCA. pass # TODO 
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 template<typename T = int> struct LCA { // vertices are represented as numbers 0->n-1. int n; vector<vector<pair<int, T> > > adjacent; LCA(int n_vertices) : n(n_vertices), adjacent(n) { } void add_edge(int u, int v, T weight=1) { adjacent[u].emplace_back(v, weight); adjacent[v].emplace_back(u, weight); } void build(int root=0) { // Once edges are added, build the tree/data structure. // TODO } int query(int u, int v, int root=-1) { // What is the lowest common ancestor of u, v? // Extension: Make this query from any root vertex you want. // TODO } T dist(int u, int v) { // Find the distance between two vertices - very simple if we have LCA. // TODO } } 

## Useful data

First off, let’s save some intermediary data that will make our life a lot easier, and strictly define the tree structure. We’ll introduce three arrays: parent, level and length.

• parent stores the direct parent of any vertex in the rooted tree.
• level stores the level of the tree the vertex is at (Number of edges from it to the root)
• length stores the length of the vertex to the root (Using edge weights).

We’ll populate these fields in the build method, since all edges should be added by then.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 class LCA: """ vertices are represented as numbers 0->n-1. """ def __init__(self, n_vertices): self.n = n_vertices self.adjacent = [[] for _ in range(self.n)] def add_edge(self, u, v, weight=1): self.adjacent[u].append((v, weight)) self.adjacent[v].append((u, weight)) def dfs(self, source, c_parent, c_level, c_length): # Search from the source down the tree and set parent, level, length accordingly. self.parent[source] = c_parent self.level[source] = c_level self.length[source] = c_length for child, weight in self.adjacent[source]: if child != c_parent: self.dfs(child, source, c_level + 1, c_length + weight) def build(self, root): # Once edges are added, build the tree/data structure. self.parent = [None]*self.n self.level = [None]*self.n self.length = [None]*self.n self.dfs(root, -1, 0, 0) def query(self, u, v, root=None): # What is the lowest common ancestor of u, v? # Extension: Make this query from any root vertex you want. pass # TODO def dist(self, u, v): # Find the distance between two vertices - very simple if we have LCA. pass # TODO 
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 template<typename T = int> struct LCA { // vertices are represented as numbers 0->n-1. int n; vector<vector<pair<int, T> > > adjacent; vi parent, level; vector<T> length; LCA(int n_vertices) : n(n_vertices), adjacent(n), parent(n), level(n), length(n) { } void add_edge(int u, int v, T weight=1) { adjacent[u].emplace_back(v, weight); adjacent[v].emplace_back(u, weight); } void dfs(int source, int c_parent, int c_level, T c_length) { // Search from the source down the tree and set parent, level, length accordingly. parent[source] = c_parent; level[source] = c_level; length[source] = c_length; for (auto v: adjacent[source]) if (v.first != c_parent) dfs(v.first, source, c_level+1, c_length+v.second); } void build(int root=0) { // Once edges are added, build the tree/data structure. dfs(root, -1, 0, 0); } int query(int u, int v, int root=-1) { // What is the lowest common ancestor of u, v? // Extension: Make this query from any root vertex you want. // TODO } T dist(int u, int v) { // Find the distance between two vertices - very simple if we have LCA. // TODO } } 

So now we can query many useful characteristics of vertices in rooted trees. Now for the interesting part: let’s start creating data unique to the LCA structure.

## Ancestor Array

LCA gets its fast queries by precomputing a special array, called ancestor. Ancestor is a 2 dimensional array with ancestor[v][k] storing the ancestor of vertex v $$2^k$$ edges towards the root. As an example, ancestor[v][0] is parent[v] (Parent is just ancestor 1 edge towards the root), and ancestor[v][1] is parent[parent[v]] where appropriate (2 edges towards root is same as parent’s parent).

If you just populated this array by searching up the tree $$2^k$$ steps each time, you’d have worst case complexity $$O(n^2)$$ to build the array. Luckily, we can use the fact that ancestor[v][k] = ancestor[ancestor[v][k-1]][k-1] (In other words, you can move $$2^k$$ steps towards the root by first moving $$2^{k-1}$$ steps, which we’ve already computed, and then another $$2^{k-1}$$ steps from this new position). This reduces the complexity to $$O(n\log_2(n))$$

We do this so that we can find the ancestor $$m$$ edges towards the root for any arbitrary $$m$$ in $$\log_2(m)$$ time, while only using $$\log_2(n)$$ space. We’ll see how this gets done later.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 class LCA: """ vertices are represented as numbers 0->n-1. """ # number such that 2^{MAX_LOG} > n. 20 works for n <= 10^6. MAX_LOG = 20 def __init__(self, n_vertices): self.n = n_vertices self.adjacent = [[] for _ in range(self.n)] def add_edge(self, u, v, weight=1): self.adjacent[u].append((v, weight)) self.adjacent[v].append((u, weight)) def dfs(self, source, c_parent, c_level, c_length): # Search from the source down the tree and set parent, level, length accordingly. self.parent[source] = c_parent self.level[source] = c_level self.length[source] = c_length for child, weight in self.adjacent[source]: if child != c_parent: self.dfs(child, source, c_level + 1, c_length + weight) def build(self, root): # Once edges are added, build the tree/data structure. self.parent = [None]*self.n self.level = [None]*self.n self.length = [None]*self.n self.dfs(root, -1, 0, 0) # NEW: Compute ancestor self.ancestor = [[-1]*self.MAX_LOG for _ in range(self.n)] # Initial step: ancestor[v][0] = parent[v] for v in range(self.n): self.ancestor[v][0] = self.parent[v] # Now, compute ancestor[v][k] from 1->MAX_LOG for k in range(1, self.MAX_LOG): for v in range(self.n): if self.ancestor[v][k-1] != -1: # Move 2^{k-1} up, then 2^{k-1} again. self.ancestor[v][k] = self.ancestor[self.ancestor[v][k-1]][k-1] def query(self, u, v, root=None): # What is the lowest common ancestor of u, v? # Extension: Make this query from any root vertex you want. pass # TODO def dist(self, u, v): # Find the distance between two vertices - very simple if we have LCA. pass # TODO 
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 template<typename T = int> struct LCA { // vertices are represented as numbers 0->n-1. // number such that 2^{MAX_LOG} > n. 20 works for n <= 10^6. int MAX_LOG = 20; int n; vector<vector<pair<int, T> > > adjacent; vi parent, level; vvi ancestor; vector<T> length; LCA(int n_vertices) : n(n_vertices), adjacent(n), parent(n), level(n), length(n) { } void add_edge(int u, int v, T weight=1) { adjacent[u].emplace_back(v, weight); adjacent[v].emplace_back(u, weight); } void dfs(int source, int c_parent, int c_level, T c_length) { // Search from the source down the tree and set parent, level, length accordingly. parent[source] = c_parent; level[source] = c_level; length[source] = c_length; for (auto v: adjacent[source]) if (v.first != c_parent) dfs(v.first, source, c_level+1, c_length+v.second); } void build(int root=0) { // Once edges are added, build the tree/data structure. dfs(root, -1, 0, 0); // NEW: Compute ancestor ancestor.assign(n, vi(MAX_LOG, -1)); // Initial step: ancestor[v][0] = parent[v] for (int v=0; v<n; v++) ancestor[v][0] = parent[v]; // Now, compute ancestor[v][k] from 1->MAX_LOG for (int k=1; k < MAX_LOG; k++) for (int v=0; v<n; v++) if (ancestor[v][k-1] != -1) { // Move 2^{k-1} up, then 2^{k-1} again. ancestor[v][k] = ancestor[ancestor[v][k-1]][k-1]; } } int query(int u, int v, int root=-1) { // What is the lowest common ancestor of u, v? // Extension: Make this query from any root vertex you want. // TODO } T dist(int u, int v) { // Find the distance between two vertices - very simple if we have LCA. // TODO } } 

## Query

That’s actually most of the ingenuity out of the way, now we can get to implementing query.

Provided we want the LCA with respect to the root we called build from, we can define the LCA l of u and v in the following way:

l is the ancestor of u and v maximising level[l].

We also know that level[l] <= min(level[u], level[v]). Using this, we can calculate query(u, v) by:

• Finding the ancestors of u and v (call them a1, a2) such that level[a1] = level[a2] = min(level[u], level[v]).
• Keep moving a1 and a2 towards the root (higher and higher ancestors) until a1 == a2. Then a1 and a2 are the LCA of u and v.

We can do both of these things on $$\log_2(n)$$ time with this ancestor array we’ve generated. Let’s see how:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 class LCA: """ vertices are represented as numbers 0->n-1. """ # number such that 2^{MAX_LOG} > n. 20 works for n <= 10^6. MAX_LOG = 20 def __init__(self, n_vertices): self.n = n_vertices self.adjacent = [[] for _ in range(self.n)] def add_edge(self, u, v, weight=1): self.adjacent[u].append((v, weight)) self.adjacent[v].append((u, weight)) def dfs(self, source, c_parent, c_level, c_length): # Search from the source down the tree and set parent, level, length accordingly. self.parent[source] = c_parent self.level[source] = c_level self.length[source] = c_length for child, weight in self.adjacent[source]: if child != c_parent: self.dfs(child, source, c_level + 1, c_length + weight) def build(self, root): # Once edges are added, build the tree/data structure. self.parent = [None]*self.n self.level = [None]*self.n self.length = [None]*self.n self.dfs(root, -1, 0, 0) self.ancestor = [[-1]*self.MAX_LOG for _ in range(self.n)] # Initial step: ancestor[v][0] = parent[v] for v in range(self.n): self.ancestor[v][0] = self.parent[v] # Now, compute ancestor[v][k] from 1->MAX_LOG for k in range(1, self.MAX_LOG): for v in range(self.n): if self.ancestor[v][k-1] != -1: # Move 2^{k-1} up, then 2^{k-1} again. self.ancestor[v][k] = self.ancestor[self.ancestor[v][k-1]][k-1] def query(self, u, v, root=None): # What is the lowest common ancestor of u, v? # Extension: Make this query from any root vertex you want. if root is not None: pass # TODO # assume that u is higher up than v, to simplify the code below if self.level[u] > self.level[v]: u, v = v, u # STEP 1: set u and v to be ancestors with the same level for k in range(self.MAX_LOG-1, -1, -1): if (self.level[v] - (1 << k) >= self.level[u]): # If v is 2^k levels below u, move it up 2^k levels. v = self.ancestor[v][k] # We can be certain that level[u] = level[v]. Reason: binary representation of all natural numbers. # Do we need to move to step 2? if (u == v): return u # STEP 2: find the highest ancestor where u != v. Then the parent is the LCA for k in range(self.MAX_LOG-1, -1, -1): if (self.ancestor[u][k] != self.ancestor[v][k]): # Move up 2^k steps u = self.ancestor[u][k] v = self.ancestor[v][k] return self.parent[u] def dist(self, u, v): # Find the distance between two vertices - very simple if we have LCA. pass # TODO 
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 template<typename T = int> struct LCA { // vertices are represented as numbers 0->n-1. // number such that 2^{MAX_LOG} > n. 20 works for n <= 10^6. int MAX_LOG = 20; int n; vector<vector<pair<int, T> > > adjacent; vi parent, level; vvi ancestor; vector<T> length; LCA(int n_vertices) : n(n_vertices), adjacent(n), parent(n), level(n), length(n) { } void add_edge(int u, int v, T weight=1) { adjacent[u].emplace_back(v, weight); adjacent[v].emplace_back(u, weight); } void dfs(int source, int c_parent, int c_level, T c_length) { // Search from the source down the tree and set parent, level, length accordingly. parent[source] = c_parent; level[source] = c_level; length[source] = c_length; for (auto v: adjacent[source]) if (v.first != c_parent) dfs(v.first, source, c_level+1, c_length+v.second); } void build(int root=0) { // Once edges are added, build the tree/data structure. dfs(root, -1, 0, 0); // NEW: Compute ancestor ancestor.assign(n, vi(MAX_LOG, -1)); // Initial step: ancestor[v][0] = parent[v] for (int v=0; v<n; v++) ancestor[v][0] = parent[v]; // Now, compute ancestor[v][k] from 1->MAX_LOG for (int k=1; k < MAX_LOG; k++) for (int v=0; v<n; v++) if (ancestor[v][k-1] != -1) { // Move 2^{k-1} up, then 2^{k-1} again. ancestor[v][k] = ancestor[ancestor[v][k-1]][k-1]; } } int query(int u, int v, int root=-1) { // What is the lowest common ancestor of u, v? // Extension: Make this query from any root vertex you want. if (root != -1) { // TODO } // assume that u is higher up than v, to simplify the code below if (level[u] > level[v]) swap(u, v); // STEP 1: set u and v to be ancestors with the same level for (int k=MAX_LOG-1, k>=0; k--) if (level[v] - (1 << k) >= level[u]) { // If v is 2^k levels below u, move it up 2^k levels. v = ancestor[v][k]; } // We can be certain that level[u] = level[v]. Reason: binary representation of all natural numbers. // Do we need to move to step 2? if (u == v) return u // STEP 2: find the highest ancestor where u != v. Then the parent is the LCA for (int k=MAX_LOG; k>=0; k--) if (ancestor[u][k] != ancestor[v][k]) { // Move up 2^k steps u = ancestor[u][k]; v = ancestor[v][k]; } return parent[u]; } T dist(int u, int v) { // Find the distance between two vertices - very simple if we have LCA. // TODO } } 

Nice! That’s the main functionality of LCA completed.

## Corrolaries

Let’s quickly tackle the two remaining implementations:

• Calculating the distance between two vertices u and v is the same as calculating the distance between u and query(u, v), and adding that to the distance between v and query(u, v)
• Calculating the LCA from a particular root, just requires a slight change in perspective. For two vertices u and v, and custom root r, the LCA will always be one of query(u, v), query(u, r) or query(v, r).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 class LCA: """ vertices are represented as numbers 0->n-1. """ # number such that 2^{MAX_LOG} > n. 20 works for n <= 10^6. MAX_LOG = 20 def __init__(self, n_vertices): self.n = n_vertices self.adjacent = [[] for _ in range(self.n)] def add_edge(self, u, v, weight=1): self.adjacent[u].append((v, weight)) self.adjacent[v].append((u, weight)) def dfs(self, source, c_parent, c_level, c_length): # Search from the source down the tree and set parent, level, length accordingly. self.parent[source] = c_parent self.level[source] = c_level self.length[source] = c_length for child, weight in self.adjacent[source]: if child != c_parent: self.dfs(child, source, c_level + 1, c_length + weight) def build(self, root): # Once edges are added, build the tree/data structure. self.parent = [None]*self.n self.level = [None]*self.n self.length = [None]*self.n self.dfs(root, -1, 0, 0) self.ancestor = [[-1]*self.MAX_LOG for _ in range(self.n)] # Initial step: ancestor[v][0] = parent[v] for v in range(self.n): self.ancestor[v][0] = self.parent[v] # Now, compute ancestor[v][k] from 1->MAX_LOG for k in range(1, self.MAX_LOG): for v in range(self.n): if self.ancestor[v][k-1] != -1: # Move 2^{k-1} up, then 2^{k-1} again. self.ancestor[v][k] = self.ancestor[self.ancestor[v][k-1]][k-1] def query(self, u, v, root=None): # What is the lowest common ancestor of u, v? # Extension: Make this query from any root vertex you want. if root is not None: # NEW: Custom root -- see diagrams below for reasoning. a = self.query(u, v) b = self.query(u, root) c = self.query(v, root) # Case 1: root is in the same component as u when a is removed from the tree. So b is the LCA if (a == c and c != b) return b # Case 2: root is in the same component as v when a is removed from the tree. So a is the LCA if (a == b and c != b) return c # Case 3: b and c are above a in the tree. So return a return a # assume that u is higher up than v, to simplify the code below if self.level[u] > self.level[v]: u, v = v, u # STEP 1: set u and v to be ancestors with the same level for k in range(self.MAX_LOG-1, -1, -1): if (self.level[v] - (1 << k) >= self.level[u]): # If v is 2^k levels below u, move it up 2^k levels. v = self.ancestor[v][k] # We can be certain that level[u] = level[v]. Reason: binary representation of all natural numbers. # Do we need to move to step 2? if (u == v): return u # STEP 2: find the highest ancestor where u != v. Then the parent is the LCA for k in range(self.MAX_LOG-1, -1, -1): if (self.ancestor[u][k] != self.ancestor[v][k]): # Move up 2^k steps u = self.ancestor[u][k] v = self.ancestor[v][k] return self.parent[u] def dist(self, u, v): # NEW: Find the distance between two vertices return self.length[u] + self.length[v] - 2 * self.length[self.query(u, v)] 
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 template<typename T = int> struct LCA { // vertices are represented as numbers 0->n-1. // number such that 2^{MAX_LOG} > n. 20 works for n <= 10^6. int MAX_LOG = 20; int n; vector<vector<pair<int, T> > > adjacent; vi parent, level; vvi ancestor; vector<T> length; LCA(int n_vertices) : n(n_vertices), adjacent(n), parent(n), level(n), length(n) { } void add_edge(int u, int v, T weight=1) { adjacent[u].emplace_back(v, weight); adjacent[v].emplace_back(u, weight); } void dfs(int source, int c_parent, int c_level, T c_length) { // Search from the source down the tree and set parent, level, length accordingly. parent[source] = c_parent; level[source] = c_level; length[source] = c_length; for (auto v: adjacent[source]) if (v.first != c_parent) dfs(v.first, source, c_level+1, c_length+v.second); } void build(int root=0) { // Once edges are added, build the tree/data structure. dfs(root, -1, 0, 0); // NEW: Compute ancestor ancestor.assign(n, vi(MAX_LOG, -1)); // Initial step: ancestor[v][0] = parent[v] for (int v=0; v<n; v++) ancestor[v][0] = parent[v]; // Now, compute ancestor[v][k] from 1->MAX_LOG for (int k=1; k < MAX_LOG; k++) for (int v=0; v<n; v++) if (ancestor[v][k-1] != -1) { // Move 2^{k-1} up, then 2^{k-1} again. ancestor[v][k] = ancestor[ancestor[v][k-1]][k-1]; } } int query(int u, int v, int root=-1) { // What is the lowest common ancestor of u, v? // Extension: Make this query from any root vertex you want. if (root != -1) { // NEW: Custom root -- see diagrams below for reasoning. int a = query(u, v); int b = query(u, root); int c = query(v, root); // Case 1: root is in the same component as u when a is removed from the tree. So b is the LCA if (a == c and c != b) return b; // Case 2: root is in the same component as v when a is removed from the tree. So a is the LCA if (a == b and c != b) return c; // Case 3: b and c are above a in the tree. So return a return a; } // assume that u is higher up than v, to simplify the code below if (level[u] > level[v]) swap(u, v); // STEP 1: set u and v to be ancestors with the same level for (int k=MAX_LOG-1, k>=0; k--) if (level[v] - (1 << k) >= level[u]) { // If v is 2^k levels below u, move it up 2^k levels. v = ancestor[v][k]; } // We can be certain that level[u] = level[v]. Reason: binary representation of all natural numbers. // Do we need to move to step 2? if (u == v) return u // STEP 2: find the highest ancestor where u != v. Then the parent is the LCA for (int k=MAX_LOG; k>=0; k--) if (ancestor[u][k] != ancestor[v][k]) { // Move up 2^k steps u = ancestor[u][k]; v = ancestor[v][k]; } return parent[u]; } T dist(int u, int v) { // NEW: Find the distance between two vertices return length[u] + length[v] - 2 * length[query(u, v)]; } } 

And that’s our implementation done! Now get out there and solve some problems!