1

enter image description here

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?

  • 5
    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

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.