# Time Limit Exceeded? (Java Solution)

• Not sure why my Java solution is exceeding the time limit. Any advice?

``````public class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
return helper(root, p, q);
}

public TreeNode helper(TreeNode root, TreeNode p, TreeNode q){
if(root==p || root==q) return root;
else{
if(dfsSearch(root.left, p) && dfsSearch(root.left, q)){
//both p and q are to the left, go left
return helper(root.left, p, q);
} else if (dfsSearch(root.right, p) && dfsSearch(root.right, q)){
return helper(root.right, p, q);
}
return root;
}
}

public boolean dfsSearch(TreeNode root, TreeNode target){
Stack<TreeNode> s = new Stack<TreeNode>();
if(root!=null) s.push(root);
TreeNode current;
while(!s.isEmpty()){
current = s.pop();
if(current==target) return true;
if(current.right!=null){
s.push(current.right);
}
if(current.left!=null){
s.push(current.left);
}
}
return false;
}
}``````

• You're repeating the DFS at each layer in the tree. So if p and q are n layers down, you would'e called DFS at each of the n layers to get to them, resulting in O(n^2) runtime.

Conceptually you only need to locate p and q once. For example you could do a DFS for p, then a DFS for q, but save the paths to each and then find where the paths diverge.

You can also do it without saving the paths with a single DFS.

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