# Find common ancestor Given X number of leaves (the ringed leaves in the picture) in an unbalanced tree with depth aroun 100-1000 and total number of nodes around 15 000 000. I'm looking for the first common ancestor for those leaves.

What is the most efficient way to achieve this?

• en.wikipedia.org/wiki/Lowest_common_ancestor has all the information you cold want. Executive summary: you can preprocess the tree in linear time to achieve constant look-up time; if the tree can change dynamically, things get more complicated. – Kilian Foth Aug 8 '14 at 7:25
• Assuming it's a dynamic tree, the most straightforward way is probably to walk from each leaf up to the root of the tree, unshifting each node onto the front of an array, then check the arrays for the index that doesn't contain the same node in each array. The node at the index before that is the lowest common ancestor. – Hey Nov 22 '14 at 18:33

## 1 Answer

Considering you already have implemented a `find` method, you can do this:

``````struct NodeBin* ancestor(struct NodeBin* n, int i, int j){ // find ancestor of i and j
struct NodeBin* ni = find(n,i);
while(ni!=NULL){
printf("%d\n",ni->data);
if(find(ni,j)!=NULL) return ni;
ni=parent(n,ni->data);
}
return NULL;
}
``````

It basically runs the `find` method using `i`'s parent as the tree's root, and if it can't find `j` from there that's not the common ancestor, then it goes one level up to `i`'s grandparent and does that recursively.

• That will recurse the same leaf multiple times and that will be slow for huge trees. – iveqy Nov 22 '14 at 7:17