Lowest Common Ancestor of a Binary Tree & Binary Search Tree

1 Node *LCA(Node *root, Node *p, Node *q) {
2   if (!root || !p || !q) return NULL;
3   if (max(p->data, q->data) < root->data)
4     return LCA(root->left, p, q);
5   else if (min(p->data, q->data) > root->data)
6     return LCA(root->right, p, q);
7   else
8     return root;
9 }

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