# Lowest Common Ancestor

here is my implementation to find the lowest common ancestor in a binary tree. It works but i would like to know if i could have done anything better or if i have missed an specific case. would really appreciate ur feedback:

//The function findOrQueue is to enqueue all elements upto target node to a queue
public void findOrQueue(Node target, Node top, LLQueue q) {
int cmp = target.getData().compareTo(top.getData());
if(cmp == 0) {
q.enqueue(top);
return ;
}
else if (cmp < 0) {
q.enqueue(top);
findOrQueue(target, top.getLeftChild(),q);
}
else {
q.enqueue(top);
findOrQueue(target, top.getRightChild(),q);
}
}

public Node LCA(Node n1, Node n2) throws QueueEmptyException {
LLQueue q1 = new LLQueue();
LLQueue q2 = new LLQueue();
findOrQueue(n1,getRoot(),q1);
findOrQueue(n2,getRoot(),q2);
Node t = null;
while (!q1.isEmpty() && !q2.isEmpty()) {
Node t1 = (Node)q1.dequeue();
Node t2 = (Node)q2.dequeue();
if(t1.getData() != t2.getData()) {
return t;
}
else t = t1;
}
if(q1.isEmpty() && q2.isEmpty())
return null;
else
return t;
}

-

## migrated from stackoverflow.comNov 20 '12 at 15:36

This question came from our site for professional and enthusiast programmers.

I would simplify the findOrQueue function to make sure it stays DRY

public void findOrQueue(Node target, Node top, LLQueue q) {
int cmp = target.getData().compareTo(top.getData());
q.enqueue(top);
if(cmp != 0) {
Node nextTop = (cmp < 0) ? top.getLeftChild() : top.getRightChild();
findOrQueue(target, nextTop, q);
}
}


Since it's used recursively, it might not be a horrible idea to keep the exit condition explicit for readability:

if(cmp == 0) {
return; // Exit condition
} else {
// ... as above
}


Edit: The return condition can also be made more direct:

boolean bothEmpty = q1.isEmpty() && q2.isEmpty();
return (!bothEmpty) ? t : null;

-
ok thnx!! but the solution looks good?? how can i extend it to binary trees and not just binary search trees?? – ueg1990 Nov 20 '12 at 20:34
You can directly write : findOrQueue(target, ((cmp < 0) ? top.getLeftChild() : top.getRightChild()), q); – cl-r Nov 21 '12 at 8:46
I actually had that originally, but thought it might be more clear in this context to make it more than a one-liner. – Eric P. Nov 27 '12 at 14:17
public Node LCA(Node top, Node n1, Node n2) {
if (top.getData() < n1.getData() && top.getData() < n2.getData()) {
return LCA(top.getLeftChild(), n1, n2);
}

if (top.getData() > n1.getData() && top.getData() > n2.getData()) {
return LCA(top.getRightChild(), n1, n2);
}