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