Find height of node 1 as h1 and height of node 2 as h2 by travelling to the root. Time O(2 lg N). If h1 > h2, then move node1 by h1 - h2 and vice versa. THen, use two pointers to move one parent at a time until parent nodes are same. Complexity - O( 3 lg N)

Assuming each node has a unique ID (its memory address, for example), you can solve this in O( 2 lg N ) where N is the number of nodes in the tree. findCommonAncestor(Node x, Node y): 1. Initialize a hashmap, call it `parentsMap`. 2. Starting from x, visit all its parents up to and including the tree root, and for each parent `p`, set parentsMap[p.id] = true 3. Starting from y, begin to visit its parents and for each parent `p`, check parentsMap[p.id]. If true, return p.id. Else, continue visiting parents until `p` is null, at which point we return null.

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