# C++_recursive_with brief analysis

• We consider a simplified case: 3 nodes : root, left, right:

• Let's consider that if the root is NULL or root == p or root==q, we should return the root;

• If not, then we search q and p from left children and right children. If we cannot find p and q, then that path will return NULL, which means that that p and q must be in the same side, then we will return the result of the other path.

• If both path is not equal to NULL, then it means that the two nodes are in different path, we directly return the root node.

• So from above analysis, we can divide this problem to smaller problems.

``````class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(root == NULL || root == p || root == q) return root;
TreeNode* tmp1 = lowestCommonAncestor(root->left, p, q);
TreeNode* tmp2 = lowestCommonAncestor(root->right, p, q);
if(tmp1 == NULL){
return tmp2;
}else if(tmp2 == NULL){
return tmp1;
}
return root;
}
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.