Algorithm to find Least Common Ancestor using recursionLet "root" be the root of given binary tree and n1 and n2 be two given nodes. If root is equal to either n1 or n2, then root is the LCA. Recursively search for LCA in left and right sub tree. If both of the recursive calls above returned non-NULL value, that means one of the node(either n1 or n2) is in left sub tree and another is in right sub tree. Hence root is the LCA.
If suppose only right sub tree returned non-Null value than both nodes are in right sub tree and right contains LCA. If suppose only left sub tree returned non-Null value than both nodes are in left sub tree and left contains LCA.
Time Complexity : O(n)