Do the binary search for both elements at the same time...as soon as their paths diverge (i.e. you have to go left for one element and right for the other) save the node where it happened...this is the lowest common ancestor...however you should still carry out the recursion to verify that both values are indeed in the tree. Complexity is same as standard binary tree search, O(log n).

To Pegasus: Your idea won't work. Usually tree nodes do not contain a parent pointer unless specified. So the recursion is top down manner.

Not binary search tree

Since it's not a binary search tree, you have to depth-first search the whole tree to find both nodes. When you find the nodes you save the path from the root to each. Then you just have to compare the two paths and find the last node in each that is the same. For instance, if the path to node G is A -> B -> C -> D -> G and the path to node H is A -> B -> E -> F -> H then the lowest common ancestor is B. Time complexity is O(n) where n is the number of nodes in the tree. Space complexity for a balanced tree is O(log(n)) since the paths can be the height of the tree.

1) Search for the node1 from root. Keep track of its path in a list. Time complexity: O(n) 2) Repeat the same for another node. 3) Now remove the common nodes from both of the list. 4) The last node before the match is your result. Time complexity: O(n) Space complexity: O(n)

Recursive call.