# Java solution : O(nlgn)

• 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);
}
}``````

• if(root == p || root == q)
return root;

This is an important part of your solution that you don't address in your summary. Without it,
[[p],[1,q]] will not return correctly.

• One average you are good, but your worst case is `O(n^2)`: each node has left only and p and q are at the lowest levels. I think it's possible `O(n)` worst/avg time.

• @mike3: You are right. It covers the case where a node can be its own ancestor

• @TWiStErRob: I am not very sure regarding the runtime complexity of this problem. But let's see. If we consider the tree to be balanced, we could traverse n/2 nodes in the 1st pass, then n/4, n/8, .., so on. So, summing up, n(1 + 1/2 + 1/4 + ... 1/(2^lgn) ) which is less than 2n (using GP). This gives us O(n).

However, if the tree is totally unbalanced (one node on each level), we could be looking (n -1) + (n - 2) + ... 1 nodes, which gives us O(n^2)

• You actually visit each node only once regardless of input in `lowestCommonAncestor` recursion, only the `prefix` method skews your runtime a lot. I suggest you try to work those into a single method and a single left-right recursion. Btw, what's the runtime score (in ms) you were given? link

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