First / Lowest common ancestor (LCA) of 2 node in binary tree

This updated information has been further expanded upon on my new website. You can find the updated details here: https://k5kc.com/cs/algorithms/lowest-common-ancestor-of-a-binary-tree/.

Problem

Case 1 - Design an algorithm and write code to find the first common ancestor of two nodes in a binary tree. Avoid storing additional nodes in a data structure. NOTE: This is not necessarily a binary search tree.
Case 2- What will you do if it is Binary search tree

Example
So for example look into below figure:

So for node 4 and 14, LCA is 8. So there are lots of solution to find it.

Solutions - Case 1 When it is not a Binary Search Tree

Method 1 - Parent pointer is given
If the graph is threaded i.e. each child has pointer to its immediate parent.

class Node{
    int value;
    Node left;
    Node right;
    Node parent;
}

1. Find list of all the elements from the nodes to the root in order.
   Example for node 4, we get {8, {20,8}}
2. Find the common element in these two lists which appears first

int getHeight(Node p) {
  int height = 0;
  while (p) {
    height++;
    p = p.parent;
  }
  return height;
}
 
// As root.parent is NULL, we don't need to pass root in.
Node LCA(Node p, Node q) {
  int h1 = getHeight(p);
  int h2 = getHeight(q);
  // swap both nodes in case p is deeper than q.
  if (h1 > h2) {
    swap(h1, h2);
    swap(p, q);
  }
  // invariant: h1 <= h2.
  int dh = h2 - h1;
  for (int h = 0; h < dh; h++)
    q = q.parent;
  while (p && q) {
    if (p == q) return p;
    p = p.parent;
    q = q.parent;
  }
  return NULL;  // p and q are not in the same tree
}

Time Complexity - O(log n)

Method 2 - Bottom up recursion(Single Traversal)

TreeNode findLCA(TreeNode root, TreeNode p, TreeNode q) {

        // no root no LCA.
        if(!root) {
                return NULL;
        }

        // if either p or q is the root then root is LCA.
        if(root==p || root==q) {
                return root;
        } else {
                // get LCA of p and q in left subtree.
                TreeNode l=findLCA(root->left , p , q);

                // get LCA of p and q in right subtree.
                TreeNode r=findLCA(root->right , p, q);

                // if one of p or q is in leftsubtree and other is in right
                // then root it the LCA.
                if(l && r) {
                        return root;
                }
                // else if l is not null, l is LCA.
                else if(l) {
                        return l;
                } else {
                        return r;
                }
        }
}

Time Complexity - O(n)

Dry running the code
Consider the 2 nodes - 4 and 14 in the diagram above, for which we have to find the LCA.

so, we call findLCA(root,4, 14)
As, root is not equal to p and q, we proceed further.
left = findLCA(8,4,14)
right = findLCA(22,4,14) - This returns nothing, and recursion of this ends here.

Now, we have
left = findLCA(4,4,14) - This returns 4 as LCA
right = findLCA(12,4,14) - this calls 2 methods - findLCA(10,4,14), findLCA(14,4,14). The latter call returns r.

Now as left and right are null, root = 8 is the LCA.

Method 3 - Storing the root to corresponding node paths
This is taken from here.
Following is simple O(n) algorithm to find LCA of n1 and n2.
1) Find path from root to n1 and store it in a vector or array.
2) Find path from root to n2 and store it in another vector or array.
3) Traverse both paths till the values in arrays are same. Return the common element just before the mismatch. 

// Finds the path from root node to given root of the tree, Stores the
// path in a vector path[], returns true if path exists otherwise false
bool findPath(Node root, ArrayList<Integer> path, int k)
{
    // base case
    if (root == null) return false;
 
    // Store this node in path vector. The node will be removed if
    // not in path from root to k
    path.add(root.data);
 
    // See if the k is same as root's key
    if (root.data == k)
        return true;
 
    // Check if k is found in left or right sub-tree
    if ( (root.left && findPath(root.left, path, k)) ||
         (root.right && findPath(root.right, path, k)) )
        return true;
 
    // If not present in subtree rooted with root, remove root from
    // path[] and return false
    path.remove();
    return false;
}
 
// Returns LCA if node n1, n2 are present in the given binary tree,
// otherwise return -1
int findLCA(Node root, int n1, int n2)
{
    // to store paths to n1 and n2 from the root
    ArrayList<Integer> path1, path2;
 
    // Find paths from root to n1 and root to n1. If either n1 or n2
    // is not present, return -1
    if ( !findPath(root, path1, n1) || !findPath(root, path2, n2))
          return -1;
 
    // Compare the paths to get the first different value 
    int i;
    for (i = 0; i < path1.size() && i < path2.size() ; i++)
        if (path1[i] != path2[i])
            break;
    return path1[i-1];
}

Solutions - Case 2 When it is a Binary Search Tree

Method 3: Take advantage of Key comparison in BST
Looking at the example tree, the lowest common ancestor to 4 and 14, the node with value 8, is different from the other ancestors to 4 and 14 in an important way. All the other ancestors are either greater than both 4 and 14 or less than both 4 and 14. Only 8 is between 4 and 14. You can use this insight to design a better algorithm.

TreeNode findFirstCommonAncestor(TreeNode root, int p, int q) {

    if (root == null) {
        return null;
    }

    if (root.value == p || root.value == q) {
        return root;
    }

    if (root.value > p && root.value > q ) {
        return findFirstCommonAncestor(root.left, p, q);
    }
    else if (root.value < p && root.value < q ) {
        return findFirstCommonAncestor(root.right, p, q);
    }
    else {
        return root;
    }
}

Time complexity - O(n)

Method 4
1. Find inorder from Root to node n1 and put in an array List L1 (O(N))
2. Find inorder from Root to node n2 and put in an array List L2 (O(N))
3. Pop head elements from each Lists to make sure the nodes themselves are not involved (cuz we only need the ancestor) 0(1)
4. Compare each element of L1 with L2 starting with the greatest index i.e. bottom. The first match is the LCA O(N)

Method 5
1. Find the inorder and the postorder elements of the range [n1,n2]
2. Find the complete postorder of the tree
3. Find out which element from list 1 comes last in list 2. This is the lowest common ancestor