# One traverse, and distinguish whether two nodes in the tree

• ``````public class Solution {
boolean flag = false;//whether both of the two are found in this tree
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root==null) return null;
TreeNode left = lowestCommonAncestor(root.left,p,q);
if(flag) return left;//the ancestor has been found
TreeNode right = lowestCommonAncestor(root.right,p,q);
if(flag) return right;
if(left!=null&&right!=null){//p and q are in the two different side, so the root is the ancestor
flag = true;//set the flag true
return root;
}else if(root==p||root==q){
if(left!=null||right!=null||p==q) flag = true;//under this situation, the root must be the ancestor
return root;
}else return left!=null?left:right;
}
}``````

• That's not O(1) space, it's O(n) space. Recursion management doesn't magically come at no cost.

• Thanks for your reminder! I have changed the title.

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