Search:

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?

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...

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??

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...

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

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...