Interview Question for Software Development Engineer at Amazon.com:

Time complexity is : O(max height of binary tree)

public void findCommonAncestor(Node current,int a,int b){

         if(current.getKey() <a && current.getKey()<b)
             findCommonAncestor(current.getRight(),a,b);
         else if (current.getKey()>a && current.getKey()>b){
             findCommonAncestor(current.getLeft(), a, b);
         }else{
             System.out.println(" least common ancestor is "+current.getKey());
         }
     }

analog76, your solution is not complete.

@clusterfudge,
what do you mean by incomplete? Can you be more precise?.

Common ancestor - first encounter of node value between a and b. Otherwise either you go left or right node.

As far as I concern it is a binary tree not binary SEARCH tree.

thanks @naipton.
1) Find matching node for the first value in the tree. If the node found create a set contains all its parents till the root.
2) Use postorder traversal for recording all the ancestor.
3) P1 is parent, P2 is grand parent and P3 is ggparent and continue till root.
   V1={P1,P2,P3,P4,....root}

4) Similary find all the parent of second value
    V2={P1,P2,P3,.root}.
5) traverse both set and first matching element in both sets is lowest common ancestor.