Greetings all !!
Have been trying to figure out a solution to this pretty common problem. There is another instance of this question in codechef forums itself (http://discuss.codechef.com/questions/14645/finding-lowest-common-ancestor-in-binary-tree). Unlike the solution presented there , the question is usually given with two integer values as input rather than two node pointers.There are tons of solutions all over the internet but I have not been able to find a correct solution till now that handles all the following cases.
-
One of the values might not be present in the tree.
-
Duplicate nodes for the same value.
-
the LCA might contain be of the input values themselves.
Any suggestions ?
Edit: One possible solution could be using the concept shown here https://www.youtube.com/watch?v=LFjCr2yDJdc. However the complexity would be O(N^2). Any possible solutions that use recursion ?