Finding Least Common Ancestor in Binary Tree

Question

Possible Duplicate:
How can I find the common ancestor of two nodes in a binary tree?
first common ancestor of a binary tree

I have a binary tree as below. I need to find the least common ancestor (LCA). e.g LCA of 6 and 4 is 1, LCA of 4 and 5 is 2.

Can anyone please suggest how should I approach and solve this problem?

http://stackoverflow.com/questions/1484473/how-can-i-find-the-common-ancestor-of-two-nodes-in-a-binary-tree — Leri, Aug 21 '12 at 13:41
A question like this one is nothing more than debatable. How far are you willing to go? Is reading a couple of papers in the field fine? Adding a library dependency generates too much overhead? Is this [tag:homework]? This can go on — Alexander, Aug 21 '12 at 13:55
http://stackoverflow.com/questions/10133332 http://stackoverflow.com/questions/5534440 http://stackoverflow.com/questions/6175020 http://stackoverflow.com/questions/3540622 http://stackoverflow.com/questions/5963802 http://stackoverflow.com/questions/6338487 http://stackoverflow.com/questions/7697042 http://stackoverflow.com/questions/3027054 http://stackoverflow.com/questions/11906132 — BlueRaja - Danny Pflughoeft, Aug 21 '12 at 14:13
You can't do better than (a) finding the paths from the root to each node then (b) identifying the longest common prefix of the two paths (the last vertex in the prefix being your nearest common ancestor). — Rafe, Aug 22 '12 at 01:41

score 15 · Accepted Answer · edited Mar 20 '14 at 23:11

Start with an ordinary depth-first search algorithm:

public Node find(Node node, int target) {
    if(node == null || node.value == target) {
        return node;
    }
    if(node.value > target) {
        return find(node.left, target);
    } else {
        return find(node.right, target);
    }
}

Now, adapt this to take two "target" parameters, target1 and target2.

When the search for target1 takes you left, and the search for target2 takes you right, you've found the LCA.

This assumes that both targets actually do exist. If you need to assert that they do, you'll need to continue the search after finding the potential LCA.

public Node findLca(Node node, int t1, int t2) {
    if(node == null) {
        return null;
    }
    if(node.value > t2 && node.value > t1) {
        // both targets are left
        return findLca(node.left, t1, t2);
    } else if (node.value < t2 && node.value < t1) {
        // both targets are right
        return findLca(node.right, t1, t2);
    } else {
        // either we are diverging or both targets are equal
        // in both cases so we've found the LCA
        // check for actual existence of targets here, if you like
        return node;
    }
}

I really like your explanation. But in the find method shouldn't you have if(node==null) return null; ? — Student, Dec 23 '14 at 22:45
@Student I have `if(node==null) return node`, which is equivalent. — slim, Dec 23 '14 at 23:13
This doesn't answer the question. You're doing depth first search, which makes no sense when trying to get the ancestors of a node as you need to traverse the parents of the nodes for LCA algorithm. DPS traverses the children of the nodes. The LCA problem is to get the least common ancestor, so you must traverse the parents. — Achilles929, May 13 '16 at 20:31

Squall · Answer 2 · 2012-08-21T14:15:58.820

1

use a list can solve your problem.

you should make a getAncestorList(). it return a list order by its ancestor eg. 4 has ancestor List [1,2] and 7 has an ancestorList [1,3]

list1 = node1.getAncestorList()
list2 = node2.getAncestorList()

minlength = min(list1.size(), list2.size())
for (int i = 0; i < minlength; i++) {
    e1 = list1.getItemAt(i);
    e2 = list2.getItemAt(i);
    if (e1 == e2) ec = e1;
}
return ec;

Because they all have the same root ancestor. so you don't need to care about the different depth. you can always find the top(n) same ancestor. and ancestor(n) is the lastest common ancestor.

edited Aug 21 '12 at 14:15

answered Aug 21 '12 at 13:44

Squall

807
1
6
9

What if the two input nodes are not at the same depth? You need a way to determine where the two ancestor lists diverge. – chepner Aug 21 '12 at 14:00
@chepner, simply, "compare each element" step needs to handle lists of different lengths. It's "find the largest number that is present in both these lists" – slim Aug 21 '12 at 14:05
*smallest* common element. Are we sure each node has a unique number? If not, there could be identical numbers in each subtree of the first common ancestor. – chepner Aug 21 '12 at 14:11
Yeah, let's be careful of what we mean by "number". Node IDs in OP's diagram always have 1 as the root, but you're right, smallest common *value*. – slim Aug 21 '12 at 14:16
we can sure the Node Object is unique. I think those "number" above is just a short name for the different Node. – Squall Aug 21 '12 at 14:24

iloahz · Answer 3 · 2012-08-21T14:00:47.680

Here's what I usually do:

first calculate f[i][j], which denotes the 2^j-th father of node i. We have

f[i][j] = f[f[i][j - 1]][j - 1]

Now we can get the j-th father of node i in log(n) time.

and we need the depth of every node, say h[i]

Above can be done in a simple dfs() with complexity of O(N*Log(N)).

then for every query(i, j) asking the LCA of node(i) and node(j), imagine two monkeys getting up in the tree, trying the get to the same node.

First make them at the same height, then we know they need to get up a same height to meet.
While they're not at the same node, climb as much as possible.
The father of the node they are currently at is the LCA.

you may refer to this:

int query(int u, int v){
    if(h[u]>h[v])swap(u,v);
    v = getUp(v,h[v]-h[u]);
    for(int i=log(n);i>=0;i--){
        if(f[u][i]!=f[v][i]){
            u=f[u][i];
            v=f[v][i];
        }
    }
    while(u!=v){
        u=f[u][0];
        v=f[v][0];
    }
    return u;
}

Here getUp(i, j) means find the j-th father of node i, as we mentioned above, which can be

int nt(int u,int x){
    for(int i=log(n);i>=0;i--){
        if((1<<i)<=x){
            u=f[u][i];
            x-=(1<<i);
        }
    }
    return u;
}

so for very query, the complexity is also O(N*Log(N)).

Finding Least Common Ancestor in Binary Tree

3 Answers3

Linked