3
\$\begingroup\$

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;
}
\$\endgroup\$

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

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

1
\$\begingroup\$

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;
\$\endgroup\$
  • \$\begingroup\$ ok thnx!! but the solution looks good?? how can i extend it to binary trees and not just binary search trees?? \$\endgroup\$ – ueg1990 Nov 20 '12 at 20:34
  • \$\begingroup\$ You can directly write : findOrQueue(target, ((cmp < 0) ? top.getLeftChild() : top.getRightChild()), q); \$\endgroup\$ – cl-r Nov 21 '12 at 8:46
  • \$\begingroup\$ I actually had that originally, but thought it might be more clear in this context to make it more than a one-liner. \$\endgroup\$ – Eric P. Nov 27 '12 at 14:17
0
\$\begingroup\$
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

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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