236. Lowest Common Ancestor of a Binary Tree

The key is to check if any one of the two target node is in left tree or right tree. The recursive function terminates at whenever encountering a target node. With this termination, it is clear that if left child subtree doesn't contain any of them, the first target is encountered in right tree will be the LCA of the other node. Therefore, we need to traverse the left subtree and the right subtree and check the result coming from the left and right subtrees.

(WRONG: I was trying to terminate one a target is found in the left subtree or in the right subtree. It is wrong because with the termination condition, you don't know if the other target node is in the same subtree or in the other.)

1:  /**  
2:   * Definition for a binary tree node.  
3:   * struct TreeNode {  
4:   *   int val;  
5:   *   TreeNode *left;  
6:   *   TreeNode *right;  
7:   *   TreeNode(int x) : val(x), left(NULL), right(NULL) {}  
8:   * };  
9:   */  
10:  class Solution {  
11:  public:  
12:    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {  
13:      if (root == NULL || root == p || root == q) return root;  
14:      TreeNode *left = lowestCommonAncestor(root->left, p, q);  
15:      TreeNode *right = lowestCommonAncestor(root->right, p, q);  
16:      return !left ? right : !right ? left : root;  
17:    }  
18:  };