Why this matters when you build with AI
Many AI products store knowledge as trees: a folder of documents, a company org chart, the parts of a product catalogue, or the steps a retrieval system took to reach an answer. A common question on such a tree is "how far apart are these two nodes?" or "which node is 3 steps up from this one?" If the tree has a million nodes and you walk up the parents for every question, the answer comes back slowly. Preparing a small table once makes each question fast.
This lesson covers that table, called binary lifting, and an alternative built from an Euler tour and a sparse table. The main risk with AI-written code for these is a wrong answer on a deep tree that a short example does not show. The code below is tested against a naive walk on random trees, and the mistakes section shows what a single wrong line does. I did not measure how often AI assistants make these errors. What I did observe is that a missing equality check or a too-small table gives answers that look reasonable on small inputs and are wrong on others.
The idea
A rooted tree has one special node, the root, and every other node has exactly one parent. The depth of a node is the number of edges from the root down to it. The root has depth 0.
An ancestor of v is any node on the path from v up to the root, including v itself. The lowest common ancestor (LCA) of u and v is the deepest node that is an ancestor of both. In the example tree below, the LCA of 3 and 4 is 1, because 1 is their deepest shared ancestor.
0
/ \
1 2
/ \ \
3 4 5
\
6Here the depths are 0 for node 0, 1 for nodes 1 and 2, 2 for nodes 3, 4 and 5, and 3 for node 6. The distance between two nodes is the number of edges on the path between them: dist(u, v) = depth[u] + depth[v] - 2 * depth[LCA(u, v)]. For nodes 3 and 4 this is 2 + 2 - 2 * 1 = 2. For nodes 3 and 6 the LCA is 0, so the distance is 2 + 3 - 0 = 5.
The k-th vertex on a path from u to v, counted from 0 at u, asks for the vertex after k steps along the path. For the path from 3 to 6, which is 3, 1, 0, 2, 5, 6, the vertex at position 3 is 2.
A naive method walks parent pointers one step at a time. That costs up to n steps per query, which is too slow when both n and the number of queries are large.
Binary lifting
Binary lifting stores jumps of size 2^b. Let up[b][v] be the 2^b-th ancestor of v. The table is built from smaller jumps: up[b][v] = up[b-1][up[b-1][v]], since two jumps of size 2^(b-1) make one jump of size 2^b. Level 0 is the parent itself, and the root's parent is set to the root, so jumps past the top stay at the root.
To find the k-th ancestor of v, read the binary digits of k. For each bit b that is 1, jump with up[b]. For example, the 5th ancestor is found by jumping 4 and then 1, because 5 is 101 in binary. Every query takes at most one jump per bit, so O(log n) jumps.
For the LCA, first lift the deeper node to the depth of the other. If they are now equal, that node is the LCA. Otherwise, try jumps from the largest level down. Take a jump on both nodes only when the two landing points differ, because then the LCA is still above them. When no jump of size 1 separates them, their parents are the LCA.
For the example, take LCA(3, 6). Node 6 is deeper, so lift it one step to node 5, which is at depth 2 like node 3. Nodes 5 and 3 differ. Jumps of size 4 and 2 both land on the root 0 for both nodes, so they are equal and skipped. The jump of size 1 gives 2 for node 5 and 1 for node 3, which differ, so the code takes them. The parents of 2 and 1 are both 0, which is the answer.
The standard technique in C++17
The code below builds the table with a breadth-first search, so it does not recurse on deep trees. It answers LCA, distance and k-th vertex on a path.
// Binary lifting for LCA, distance, k-th ancestor and k-th vertex on a path.
// Input: n q, then n-1 edges "u v" (0-based), then q queries:
// "1 u v" -> print dist(u, v)
// "2 u v k" -> print the vertex at position k (0-based) on the path u -> v
#include <bits/stdc++.h>
using namespace std;
struct BinaryLifting {
int n, LOG;
vector<int> depth;
vector<vector<int>> up; // up[b][v] = the 2^b-th ancestor of v; the root's parent is the root
BinaryLifting(int n_, const vector<vector<int>>& adj, int root) : n(n_) {
LOG = 1;
while ((1 << LOG) <= n) LOG++;
depth.assign(n, -1);
up.assign(LOG, vector<int>(n, root));
vector<int> order; // BFS order, so no recursion is needed
order.reserve(n);
depth[root] = 0;
order.push_back(root);
for (size_t i = 0; i < order.size(); i++) {
int u = order[i];
for (int w : adj[u]) {
if (depth[w] == -1) {
depth[w] = depth[u] + 1;
up[0][w] = u;
order.push_back(w);
}
}
}
for (int b = 1; b < LOG; b++)
for (int v = 0; v < n; v++) up[b][v] = up[b - 1][up[b - 1][v]];
}
// k-th ancestor of v. Assumes 0 <= k <= depth[v].
int kth(int v, int k) const {
for (int b = 0; b < LOG; b++)
if ((k >> b) & 1) v = up[b][v];
return v;
}
int lca(int u, int v) const {
if (depth[u] < depth[v]) swap(u, v);
u = kth(u, depth[u] - depth[v]); // lift the deeper vertex to the same depth
if (u == v) return u;
for (int b = LOG - 1; b >= 0; b--) {
if (up[b][u] != up[b][v]) { // both jumps stay below the LCA
u = up[b][u];
v = up[b][v];
}
}
return up[0][u];
}
int dist(int u, int v) const { return depth[u] + depth[v] - 2 * depth[lca(u, v)]; }
// Vertex at position k (0-based) on the path from u to v, with 0 <= k <= dist(u, v).
int onPath(int u, int v, int k) const {
int w = lca(u, v);
int d1 = depth[u] - depth[w]; // number of edges from u up to w
if (k <= d1) return kth(u, k);
return kth(v, dist(u, v) - k);
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, q;
cin >> n >> q;
vector<vector<int>> adj(n);
for (int i = 0; i < n - 1; i++) {
int a, b;
cin >> a >> b;
adj[a].push_back(b);
adj[b].push_back(a);
}
BinaryLifting bl(n, adj, 0);
while (q--) {
int t;
cin >> t;
if (t == 1) {
int u, v;
cin >> u >> v;
cout << bl.dist(u, v) << '\n';
} else {
int u, v, k;
cin >> u >> v >> k;
cout << bl.onPath(u, v, k) << '\n';
}
}
return 0;
}The table needs LOG levels so that 2^LOG is greater than n. A depth can be as large as n - 1, and the bits of any depth up to n - 1 must fit in the levels. The loop while ((1 << LOG) <= n) LOG++ gives that.
The Euler tour with a sparse table
There is a second method that answers LCA in constant time after preprocessing. Walk the tree with a depth-first search and write down each node every time you enter it and every time you come back to it from a child. A tree with n nodes gives a sequence of 2n - 1 entries. For the example tree, the sequence starts 0, 1, 3, 1, 4, 1, 0, 2, 5, 6, 5, 2, 0. Between the first appearances of u and v, the shallowest node in the sequence is their LCA. A sparse table answers "shallowest entry in a range" in constant time after an O(m log m) build over m entries. Here m = 2n - 1.
This method does not give the k-th vertex on a path directly. Use binary lifting when you need that query. The code below is the Euler version of the structure, with the same input format as the code above, but it prints distances only.
// LCA with an Euler tour and a sparse table over depths (O(n log n) build, O(1) query).
struct EulerLCA {
vector<int> dep, first, euler, lg;
vector<vector<int>> sp; // sp[k][i] = vertex of minimum depth in euler[i .. i + 2^k - 1]
EulerLCA(int n, const vector<vector<int>>& adj, int root) : dep(n, 0), first(n, -1) {
vector<int> par(n, -1), it(n, 0), st;
st.push_back(root);
first[root] = 0;
euler.push_back(root);
while (!st.empty()) { // iterative DFS
int u = st.back();
if (it[u] < (int)adj[u].size()) {
int w = adj[u][it[u]++];
if (w == par[u]) continue;
par[w] = u;
dep[w] = dep[u] + 1;
first[w] = (int)euler.size();
euler.push_back(w);
st.push_back(w);
} else {
st.pop_back();
if (!st.empty()) euler.push_back(st.back()); // step back to the parent
}
}
int m = (int)euler.size(); // 2n - 1
lg.assign(m + 1, 0);
for (int i = 2; i <= m; i++) lg[i] = lg[i / 2] + 1;
int K = lg[m] + 1;
sp.assign(K, vector<int>(m, 0));
for (int i = 0; i < m; i++) sp[0][i] = euler[i];
for (int k = 1; k < K; k++)
for (int i = 0; i + (1 << k) <= m; i++) {
int a = sp[k - 1][i], b = sp[k - 1][i + (1 << (k - 1))];
sp[k][i] = dep[a] <= dep[b] ? a : b;
}
}
int lca(int u, int v) const {
int l = first[u], r = first[v];
if (l > r) swap(l, r);
int k = lg[r - l + 1];
int a = sp[k][l], b = sp[k][r - (1 << k) + 1];
return dep[a] <= dep[b] ? a : b;
}
int dist(int u, int v) const { return dep[u] + dep[v] - 2 * dep[lca(u, v)]; }
};The main function for this version reads the same input. It prints the answer to each type-1 query and skips the type-2 lines.
Running the example
Save this tree and queries as tree_small.txt. The tree has 7 nodes, rooted at 0, and it is the example tree above:
7 5
0 1
0 2
1 3
1 4
2 5
5 6
1 3 4
1 3 6
2 3 6 0
2 3 6 3
2 4 6 4Running the binary lifting program:
2
5
3
2
5The first two lines are distances: dist(3, 4) = 2 and dist(3, 6) = 5. The next three are path vertices. The path from 3 to 6 is 3, 1, 0, 2, 5, 6, so position 0 is 3 and position 3 is 2. The path from 4 to 6 is 4, 1, 0, 2, 5, 6, so position 4 is 5.
The Euler version prints the distances for the first two queries only. Save only the first two query lines (type 1) and the header line with the count changed to 2, then run it:
2
5For the chain input, the same program is run as ./lift < chain_big.txt on a path of 200000 nodes with 200000 distance queries. The total time was 0.385 s on the machine I used, measured once with time. Your machine will give a different number.
A short Python reference
The naive method is useful as the reference for testing. It climbs parents from both nodes and does not share code with the fast version. This sample is runnable.
Its output, from my run:
3 4 lca 1 dist 2
3 6 lca 0 dist 5
4 6 lca 0 dist 5Complexity
Binary lifting uses O(n log n) time and memory to build. With n = 200000 it has 18 levels, so the table has about 3.6 million integers, roughly 14 MB with 4-byte integers. A query takes O(log n) time, one jump per bit.
The Euler method uses an Euler sequence of 2n - 1 entries and a sparse table with about log(2n) levels, so O(n log n) time and memory to build. A distance query takes O(1) time, with two table reads and a comparison. For n = 200000 the table has about 19 levels of 400000 integers each, roughly 30 MB with 4-byte integers. These sizes are computed from the formulas, not measured.
A naive walk costs O(depth) per query. On a path graph with 200000 nodes that is up to 200000 steps per query, so the naive method is only for testing.
Hands-on exercise
Do this on your own machine.
- Save the binary lifting code as
lift.cpp, compile it withg++ -O2 -std=c++17 -o lift lift.cpp, and run it ontree_small.txt. Your output must match the output above. - Write a naive version in Python that reads the same input and answers each query by walking parents, as in the reference sample. Make it print the same format.
- Generate 300 random trees with up to 12 nodes and 40 queries each. Use a random parent for each node from 0 to i - 1, and include some chain-like trees where the parent is among the last three nodes. Run both programs on each and report every mismatch with the input that caused it.
- Mutate one line on purpose, for example delete the
if (u == v) return u;line, and check that your test finds the change. A test that never fails on a deliberate bug is not testing anything.
Common mistakes
These mistakes produced wrong answers in my tests. The outputs below are from my runs.
Missing equality check in the LCA. After lifting the deeper node to the same depth, the two nodes may already be the same, which means one is an ancestor of the other. Without if (u == v) return u; the jump loop never moves, because the two nodes are equal at every level. It then returns the parent of the lifted node. I removed that line in a copy and queried the pair (1, 3) on tree_small.txt, which is distance 1 because node 1 is the parent of node 3. The correct program prints 1, and the copy printed 3, because it reported the wrong LCA, 0, and added the depths. Test pairs where one node is an ancestor of the other.
Table too small. If LOG is fixed at a small value, a deep node cannot be lifted to the root. I built a copy of the program with LOG fixed at 2 and ran it on a path of 9 nodes, 0 to 8, with the query "distance from 0 to 8." The correct answer is 8. The copy printed 0. The fix is the loop while ((1 << LOG) <= n) LOG++, so the levels cover depths up to n - 1.
Root's parent not set to itself. If the root's parent is left as -1, a jump past the root reads index -1. In C++ this is undefined behaviour and can crash or return garbage. The code sets every entry in up[b] to the root before the BFS, which keeps jumps past the top at the root. I did not run a copy with -1 to see the exact symptom.
Wrong Euler tour length. An Euler tour has 2n - 1 entries, not n. A sparse table built over n entries misses the second visits, and the LCA can come back as a node below the true one. I did not run a broken copy for this lesson; the length follows from the rule that each edge is walked down once and up once.
Forgetting the swap in the Euler query. first[u] may be larger than first[v]. The range must be taken as the smaller index to the larger, which the code does with if (l > r) swap(l, r);. Without it the range is empty, and the table lookup reads the wrong entry.
Checklist
- Write the tree with a clear root, and check that the input has n - 1 edges.
- Build the parent and depth tables with a breadth-first search, so no recursion is needed.
- Set the root's parent to the root.
- Choose
LOGso that 2^LOG is greater than n. - Lift the deeper node first, then check for equality before the jump loop.
- Compute distance as depth[u] + depth[v] - 2 * depth[LCA].
- For k-th vertex on a path, split the path at the LCA and lift from the correct side.
- Test every query type against a naive walk on random trees, including chain-like trees and pairs where one node is an ancestor of the other.
Practice
Practice 1: LCA and distance by hand
Using tree_small.txt, find the LCA of 5 and 4, and the distance between them.
Hint: find the depth of each node first. Then walk up from each node until the paths meet.
Show the answer
The LCA is 0, because 5 is under 2, which is under 0, and 4 is under 1, which is under 0. Depths are 2 and 2, so the distance is 2 + 2 - 2 * 0 = 4. The path is 5, 2, 0, 1, 4.
Practice 2: k-th vertex on a path
Using tree_small.txt, what is the vertex at position 2 on the path from 6 to 3?
Hint: write out the whole path first. Count from 0 at node 6.
Show the answer
The path from 6 to 3 is 6, 5, 2, 0, 1, 3. Position 0 is 6, position 1 is 5, and position 2 is 2. The answer is 2.
Practice 3: how many levels
For n = 200000, what is the smallest LOG where 2^LOG is greater than n?
Hint: 2^17 is 131072 and 2^18 is 262144. Compare each with 200000.
Show the answer
LOG = 18. 2^17 = 131072 is not greater than 200000, but 2^18 = 262144 is, so 18 levels cover every depth up to 199999.
Practice 4: find the bug
Remove the line if (u == v) return u; from the LCA function and find a query on tree_small.txt that gives a wrong answer. Say what the program prints and what it should print.
Hint: pick a pair where one node is an ancestor of the other, such as a node and one of its children.
Show the answer
The query 1 1 3 (distance from 1 to 3) is one such case. The correct program prints 1, because 1 is the parent of 3. The copy without the line prints 3, because it returns the parent of 1, which is 0, and the distance formula then gives 1 + 2 - 0 = 3.
Summary
Binary lifting stores ancestors at power-of-two distances. Preparing this table takes O(n log n) time, and each LCA, distance or k-th vertex query takes O(log n) time. An Euler tour with a sparse table answers LCA and distance in constant time after the same preparation, but it does not answer k-th vertex queries. The main errors are a missing equality check, a table with too few levels, and a root without a parent of its own. A naive walk on random trees finds all three.