Recently, I was solving a tree problem that required finding the k-th ancestor of a node in a rooted tree and LCA (lowest common ancestor) of any two nodes quickly. I knew binary lifting does both of those things in O(log n) time, but I didn't know exactly how it worked. So I tried to think of a different approach, and came up with the following algorithm. The algorithm uses the concept of DFS arrival times and binary search, which I find easier to think about than binary lifting. It finds the k-th ancestor of any node in O(log n) time and LCA of any two nodes in O(log2 n) time (hence the "kind of" in the title).
Implementation:
Let us use the following example tree.
In this example, the DFS arrival times and node indices are the same for simplicity.
Setup:
Run DFS from the root. On arriving each node record the arrival time of that node (tin), the reverse mapping from arrival time to nodes (rev), and the depth of each node (d). Also, for each depth, record which arrival times occur at that depth (arrival_times).
int n = 6; // in this case number of nodes in the tree is 6 (nodes -> {0 .. 5}, 0 is the root)
vector<vector<int>> tree = {{1, 2}, {0}, {0, 3, 4}, {2}, {2, 5}, {4}};
vector<int> tin(n), rev(n), d(n);
vector<vector<int>> arrival_times(n); // however we only need first max_depth elements of this 2D array
int time = 0; // arrival time of the root would be 0
void Dfs (int node, int parent, int depth) {
tin[node] = time;
rev[time] = node;
d[node] = depth;
arrival_times[depth].push_back(time);
time += 1;
for (int child : tree[node]) {
if (child != parent) {
Dfs(child, node, depth + 1);
}
}
}
Dfs(0, -1, 0); // Running Dfs from root
In our example, arrival_times will turn out to be {{0}, {1, 2}, {3, 4}, {5}, {}, {}}.
This setup takes O(n) time and O(n) space.
Finding the kth ancestor of a node x:
Fact 1: Each array in arrival_times is in ascending order.
Fact 2: In DFS traversal, the arrival time of any ancestor of a node is always less than the arrival time of that node.
Fact 3: The depth of the kth ancestor of x is d[x] - k. (the ancestor doesn't exist if depth of x is less than k)
Fact 4: At any depth smaller than or equal to the depth of x, the node with the largest arrival time that is smaller than or equal to the arrival time of x is an ancestor of x.
Given these facts, the kth ancestor can be found using binary search as given below:
int da = d[x] - k; // depth of kth ancestor
int kth_ancestor;
if (da >= 0) {
kth_ancestor = rev[*prev(upper_bound(arrival_times[da].begin(), arrival_times[da].end(), tin[x]))];
}
else {
kth_ancestor = -1; // does not exist
}
Just one binary search operation, so it takes O(log n) time.
Finding LCA of any two nodes x and y:
Run binary search to find the maximum depth such that the ancestors of both x and y at that depth are the same node.
int lo = 0, hi = min(d[x], d[y]);
while (lo < hi) {
int mid = (lo + hi + 1) / 2;
int anc_x = *prev(upper_bound(arrival_times[mid].begin(), arrival_times[mid].end(), tin[x]));
int anc_y = *prev(upper_bound(arrival_times[mid].begin(), arrival_times[mid].end(), tin[y]));
if (anc_x == anc_y) {
lo = mid;
}
else {
hi = mid - 1;
}
}
int lca = rev[*prev(upper_bound(arrival_times[lo].begin(), arrival_times[lo].end(), tin[x]))];
Here, we run binary search and, in each iteration we run another binary search to find ancestors of x and y at depth mid. Hence time complexity would be O(log2 n).
I don’t know if this algorithm is already known or not. In either case, I thought writing this blog might help people who aren’t familiar with any algorithm for finding the k-th ancestor and LCA in a tree efficiently, such as binary lifting, or who find writing the code for it annoying, or who just want to know what other ways exist to achieve the same goal.
Hope you found this interesting :)
