Find least common ancestor of two nodes in java

Question

I have looked at a lot of other answers on stackoverflow and can't find anything that works, I either get the root, or node1 itself returned, I'm not sure how to do this recursively and have tried it many times all ending the same way. Any help would be greatly appreciated!

Here's my code:

private static Node findLCA(Node node1, Node node2) {
    Node temp1 = node1, temp2 = node2, currentLargest = null;
    int largestDepth = 0;
    boolean found = false;
    if(node1 == null || node2 == null){
        return null;
    } else{
        while(found == false){
            if(temp1.getParent() != null && temp2.getParent() != null && temp1.getParent() == temp2.getParent() && nodeDepth(temp1.getParent()) > largestDepth){
                largestDepth = nodeDepth(temp1.getParent());
                currentLargest = temp1;
                temp1 = temp1.getParent();
                temp2 = temp2.getParent();
            } else if(temp1.getParent() != null){
                temp1 = temp1.getParent();
            } else if(temp2.getParent() != null){
                temp2 = temp2.getParent();
            }
            if(temp1.getParent() == null && temp2.getParent() == null){
                found = true;
            }

        }
        if(nodeDepth(temp1) >= largestDepth){
            return temp1;
        } else{
            return currentLargest;
        }
    }
}

I edited it to make a list of ancestors of each node, but I'm not sure how to go around checking each one to see if the elements in the list's match up since they are usually different sizes.

Heres the new code:

ArrayList<PhyloTreeNode> list1 = new ArrayList<PhyloTreeNode>();
    ArrayList<PhyloTreeNode> list2 = new ArrayList<PhyloTreeNode>();

    if(node1 == null || node2 == null){
        return null;
    } else{
        if(node1.getParent() != null){
            list1.add(node1.getParent());
            findLeastCommonAncestor(node1.getParent(), node2);
        }
        if(node2.getParent() != null){
            list2.add(node2.getParent());
            findLeastCommonAncestor(node1, node2.getParent());
        }
    }

Just get lists of ancestors for both nodes and find the last one they have in common. — user2357112, Dec 06 '13 at 06:10
Possible duplicate of http://stackoverflow.com/questions/1484473/how-to-find-the-lowest-common-ancestor-of-two-nodes-in-any-binary-tree — aga, Dec 06 '13 at 06:10
aga, I've looked at that and it's somewhat helpful but I'm still not able to figure it out with the answers on that. and @user2357112 take 2 lists one with populated with node1.getParent() until the root is hit, and same with node2, then do I get the one thats equal near the beginning of the list, or the end? Say there's the two list of ancestors of node1 and node2, list1.get(0) == list2.get(0) is that > or < list1.get(0) == list2.get(3)? — Molten, Dec 06 '13 at 06:13
Iterate over both lists in parallel, starting from whichever end you put the root. As soon as the lists diverge, you know that the node right before the divergence is the lowest common ancestor. — user2357112, Dec 06 '13 at 06:19
@user2357112 I updated the main question with the lists of the ancestors of each node, but i'm not sure how to iterate through them in parallel and return the node right before they diverge since they are usually different length lists. I tried having a double for loop that checked to see if the first element of the first list was equal to the first element of the second list etc. Then when they weren't equal return that element - 1. But that didn't work out so well. — Molten, Dec 06 '13 at 07:01

score 0 · Answer 1 · answered May 15 '15 at 18:45

We can use recursive post order traversal for computing lowest common ancestor, Here is my Java implementation Here a & b are given input data for which i have to find lowest common ancestors.

public static int lowestcommanancestors(Node root,int a,int b){
 if(root==null)
  return 0;
 int x=lowestcommanancestors(root.left,a,b);
 int y=lowestcommanancestors(root.right,a,b);
 if(x+y==2){
  System.out.println(root.getData());
  return 0;
 }
 if(root.getData()==a || root.getData()==b){
  return x+y+1;
 }
 else{
  return x+y;
 }
 
}

First i am checking whether given input node presenting in left subtree or not,if yes just return 1 else 0,Similarly for right sub tree.When sum becomes 2 first time that node will be lowest common ancestors. Tell me if i am wrong or you are getting difficulties to understanding the code

Find least common ancestor of two nodes in java

1 Answers1