Thread: Lowest Common Ancestor in Binary Tree

Following is my implementation of lowest common ancestor for a Binary Search tree. I have two question:

1) The time complexity is O(n) and space complexity is O(n) worse case but O(logn) average case for both time and space if BST is balanced. is that correct?
2) How can i extend my solution to binary trees and not just binary search trees.

Hope to hear from you soon.

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

doesnt bottom-up mean, i will need a parent pointer??

so lets stay i have a parent pointer, i still have to traverse to the two nodes whose LCA i am calculating...so how will bottom-up help me?? can u plz help me with this?

--- Update ---

or are we assuming we already know the location of the the two nodes and that all the values in the nodes are distinct??

can u plz give an example of how to do bottom up traversal?? i dont understand how to build traversal bottom-up without knowing where the node is??

ok, so my findOrQueue function does that....it finds the node first and then as it does find it, it adds the others nodes in its path to a queue....which part r u referring to with respect to bottom-up approach??

ok, i have one question abt bottom-up traversal, do it go uptill leaves and then up to the nodes i am calculating LCA for? and from there i go to the root?