Finding least common ancestor of two nodes

Question:

For a binary tree (not BST), this can be done by getting the paths from root to both the nodes and then outputting the node where the path differ for the first time. Can we do better ?

Answer:

Node* LCA(Node *R,Node* P,Node* Q)
{
  if(R == NULL)
        return NULL;
  if(R->left == P || R->right == Q
    || R->left == Q || R->right == P)
      return R;
  Node *f = LCA(R->left,P,Q);
  Node *s = LCA(R->right,P,Q);
  if(f!=NULL && s !=NULL)
        return R;
  else
    return (f == NULL)?s:f;
}

 

 

code.. Explanation :

 

 

I think the code algorithm is as follows:

Inputs: a Root R, two nodes (P, Q) to search for a LCA

Algo: function LCA (R, P, Q)
 - if R is NULL return
 - if the R->left is (P or Q) , or the R->Right is (P or Q)
        then we have the LCA = R and return it
  else --then no node (P or Q) is found as a direct child of R) --
      - search for LCA of (P and Q) using the R->Left as root , call it F
      - search for LCA of (P and Q) using the R->Right as root , call it S

      if (F is LCA AND also S is LCA -not NULLS-)
          this means that we have one of the nodes (P or Q) on the left OR right of R (say Right), AND the other node on the Other Side of R (say left)
      so the Root R is the LCA for (P, Q) -- because it is impossible that we will find another node after further  "Depth First Search" such that P , Q exists on left and right of it

      else if ONLY F is LCA then both (P, Q) are found on the LEFT of R and F is the LCA of them

      else if ONLY S is LCA then both (P, Q) are found on the Right of R and S is the LCA of them