Least Common Ancestor in a tree

Given two nodes of a tree, find the least common ancestor.

Case I : Each node has a pointer to its parent node.

Case II : A Binary Search Tree.

Case III : A Normal Binary Tree.

Example:

                          10
                        /     \
                       5       20
                    /    \       \
                   3     6        [21]
                                 /   \
                                15    {30}
                              /  \     /  \
                            13   {16} 25  35
                                   \
                                    17

Least common ancestor of 16, 30 is 21.

Solution:

Case I: Similar to finding the intersection of two linked lists. O(log(n)) complexity

Case II:

/**
 * Find the least common ancestor in a Binary search tree, 
 * assuming n1->val < n2->val
 * NOTE : In a BST there can be only one node between two given values.
 * */
Node* FindLCA_BST(Node *root, Node *n1, Node *n2)
{
    if ( !root )
        return NULL;
    if ( (root->val <= n2->val) && (root->val >= n1->val) )
        return root;
    else if (root->val < min)
    {
        /* goto right, a higher value */
        return FindLCA_BST(root->right);
    }
    else
    {
        return FindLCA_BST(root->left);
    }

}

Case III:

/** Find the Least common ancestor for any given binary tree
 * and two nodes n1, and n2 and either n1 or n2 can be an ancestor
 * of one another.
 * */
bool FindLCA(Node *root, Node* n1, Node* n2, Node** lca)
{
    if(!root)
        return false;
    else
    {
        // Is the current node one of the required nodes;
        bool isCur = (n1 == root) || (n2 == root);
        // check the left subtree
        bool isLeft = FindLCA(root->left, n1, n2, lca);
        // check the right subtree
        bool isRight = FindLCA(root->right, n1, n2, lca);

        if ( (isLeft && isRight)  // both the nodes occur as the children of given node
                || (isCur && isLeft) // either of n1 or n2 is the ancestor of the other.
                || (isCur && isRight) 
            )
        {
            *lca = root;
            return true;
        }
        else
            return isLeft || isRight || isCur; // Let the parent decide the result.
    }
}