LCA or Lowest Common Ancestor of a Binary Tree

Problem:
Given a binary tree, find the lowest common ancestor of two given nodes in the tree.

E.g.:

        _______3______
       /              \
    ___5__          ___1__
   /      \        /      \
   6      _2       0       8
         /  \
         7   4

In this tree, an LCA for 6 and 4 is 5. For 5 and 4 it is 5,too. For 7 and 1 it is 3. And so on.

Solution:
A Bottom-up Approach:
We traverse from the bottom, and once we reach a node which matches one of the two nodes, we pass it up to its parent. The parent would then test its left and right subtree if each contain one of the two nodes. If yes, then the parent must be the LCA and we pass its parent up to the root. If not, we pass the lower node which contains either one of the two nodes (if the left or right subtree contains either p or q), or NULL (if both the left and right subtree does not contain either p or q) up.

Node *LCA(Node *root, Node *p, Node *q) {
  if (!root) return NULL;
  if (root == p || root == q) return root;
  Node *L = LCA(root->left, p, q);
  Node *R = LCA(root->right, p, q);
  if (L && R) return root;  // if p and q are on both sides
  return L ? L : R;  // either one of p,q is on one side OR p,q is not in L&R subtrees
}

Complexity:

time - O(n)
space - O(log n)

Links and credits:
http://leetcode.com/2011/07/lowest-common-ancestor-of-a-binary-tree-part-i.html