Following logic is used in the solution:-

Traverse through every element of the left side of the root.

If both p and q are found, move left. If none are found, move right. If only one of them is found, root is the answer.

Assuming that tree is sufficiently balanced, traversing takes n/2 time and we repeat this logn time.

A good catch is to compare the TreeNode reference and not their values, since multiple nodes can have same value and we may get false positive! Below is the code :-

```
public class Solution {
boolean foundP = false;
boolean foundQ = false;
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == p || root == q)
return root;
prefix(root.left, p, q);
if(foundP && foundQ) {
foundP = foundQ = false;
return lowestCommonAncestor(root.left, p, q);
} else if(!foundP && !foundQ)
return lowestCommonAncestor(root.right, p, q);
return root;
}
void prefix(TreeNode root, TreeNode p, TreeNode q) {
if(root == null)
return;
if(root == p)
foundP = true;
else if(root == q)
foundQ = true;
prefix(root.left, p, q);
prefix(root.right, p , q);
}
}
```