The following is the fastest way to solve this . Space complexity O(1) , Time complexity O(n). If
If a node has both left and right value as not null, then that node is your answer(3rd 'if' from top). While iterating if a value is found, as all the values are uniques and must be present, we don't need to search its descendants. so just return the found node that matched. if a node's both left and right branch contents null propagate null upwards. when reached top-level recursion, if one branch returned value, others do not keep propagating that value, when both returned not null return current node. If it reaches root level recursion with one null and another not null, return not null value, as the question, promises the value exists, it must be in the children tree of the found node which we never traversed.
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null) return null;
if(root.val == p.val || root.val == q.val) return root;
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if (left != null && right !=null) return root;
if (left == null && right ==null) return null;
return (left != null ? left : right);
}
}