Lowest common ancestor in binary tree

binary-tree
traversal
tree

#1

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.

  1. One of the values might not be present in the tree.

  2. Duplicate nodes for the same value.

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


#2

go to link Static Trees this will help you more than you need now.