Lowest Common Ancestor

Question

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;
}

Answer 1

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;

Answer 2

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);
    }

    return top;
}

Frankly, I don't understand what you are trying to do with LLQ's.

For general trees the answer is not trivial, see http://en.wikipedia.org/wiki/Lowest_common_ancestor