Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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;
}
share|improve this question

migrated from stackoverflow.com Nov 20 '12 at 15:36

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

2 Answers 2

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;
share|improve this answer
    
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. –  E-Man 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);
    }

    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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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