Tree Algorithms

Lowest Common Ancestor

There are many ways to solve the LCA problem.

Resources

• LCA – Lowest Common Ancestor by Errichto
• Episode 28 - Sparse Tables and LCA by Algorithms Live
• https://cp-algorithms.com/graph/lca.html

Two main approaches

1. Binary Lifting, $O(N\log N)$ preprocessing, $O(\log N)$ for each query
2. Sparse Table, $O(N\log N)$ preprocessing, $O(1)$ for each query

Hmm, these are the Competitive Programming approaches. But for regular LeetCode, one of the ways you can approach this is doing it recursively.

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
	if (root == nullptr) {
		return nullptr;
	}
	if (root == p || root == q) {
		return root;
		
	}
	TreeNode* l = lowestCommonAncestor(root->left, p,q);
	TreeNode* r = lowestCommonAncestor(root->right, p,q);
	
		
	if (l && r) {
		return root;
	} else if (l){
		return l;
	} else if (r) {
		return r;
	} else {
		return nullptr;
	}

1. Binary Lifting

Erritcho gave a tutorial about this technique, as well as Algorithms Live. Think about it like a Binary Search on trees.

Binary lifting requires $O(N\log N)$ for preprocessing the tree, and then $O(\log N)$ for each LCA query.

up[i][j] is the 2^j-th ancestor above the node i

tin = time in (of first visit) tout = time out (time we left) Since we do DFS, we can use this information to determine in constant time if a node is an ancestor of another node. Does this have to do with the Euler Tour?

int n, l;
vector<vector<int>> adj;
 
int timer;
vector<int> tin, tout;
vector<vector<int>> up;
 
void dfs(int v, int p)
{
    tin[v] = ++timer;
    up[v][0] = p;
    for (int i = 1; i <= l; ++i)
        up[v][i] = up[up[v][i-1]][i-1];
 
    for (int u : adj[v]) {
        if (u != p)
            dfs(u, v);
    }
 
    tout[v] = ++timer;
}
 
bool is_ancestor(int u, int v)
{
    return tin[u] <= tin[v] && tout[u] >= tout[v];
}
 
int lca(int u, int v)
{
    if (is_ancestor(u, v)) return u;
    if (is_ancestor(v, u)) return v;
    for (int i = l; i >= 0; --i) {
        if (!is_ancestor(up[u][i], v))
            u = up[u][i];
    }
    return up[u][0];
}
 
void preprocess(int root) {
    tin.resize(n);
    tout.resize(n);
    timer = 0;
    l = ceil(log2(n));
    up.assign(n, vector<int>(l + 1));
    dfs(root, root);
}
 

2. Sparse Table

This idea is first built on the Euler Tour technique. We reduce the LCA problem down to a RMQ problem, which is then solved using a sparse table.

The code below implements LCA for a Segment Tree. It seems a bit more complicated…

struct LCA {
    vector<int> height, euler, first, segtree;
    vector<bool> visited;
    int n;
 
    LCA(vector<vector<int>> &adj, int root = 0) {
        n = adj.size();
        height.resize(n);
        first.resize(n);
        euler.reserve(n * 2);
        visited.assign(n, false);
        dfs(adj, root);
        int m = euler.size();
        segtree.resize(m * 4);
        build(1, 0, m - 1);
    }
 
    void dfs(vector<vector<int>> &adj, int node, int h = 0) {
        visited[node] = true;
        height[node] = h;
        first[node] = euler.size();
        euler.push_back(node);
        for (auto to : adj[node]) {
            if (!visited[to]) {
                dfs(adj, to, h + 1);
                euler.push_back(node);
            }
        }
    }
 
    void build(int node, int b, int e) {
        if (b == e) {
            segtree[node] = euler[b];
        } else {
            int mid = (b + e) / 2;
            build(node << 1, b, mid);
            build(node << 1 | 1, mid + 1, e);
            int l = segtree[node << 1], r = segtree[node << 1 | 1];
            segtree[node] = (height[l] < height[r]) ? l : r;
        }
    }
 
    int query(int node, int b, int e, int L, int R) {
        if (b > R || e < L)
            return -1;
        if (b >= L && e <= R)
            return segtree[node];
        int mid = (b + e) >> 1;
 
        int left = query(node << 1, b, mid, L, R);
        int right = query(node << 1 | 1, mid + 1, e, L, R);
        if (left == -1) return right;
        if (right == -1) return left;
        return height[left] < height[right] ? left : right;
    }
 
    int lca(int u, int v) {
        int left = first[u], right = first[v];
        if (left > right)
            swap(left, right);
        return query(1, 0, euler.size() - 1, left, right);
    }
};

Related

• Sparse Table
• Euler Tour