# Python solution in O(n) (update to faster version)

• ``````def cover(self, root, target):
if root == None:
return False
if root == target:
return True
return self.cover(root.left, target) or self.cover(root.right, target)

def lowestCommonAncestor(self, root, p, q):
if root == None or root == p or root == q:
return root

if self.cover(p, q):
return p
if self.cover(q, p):
return q

def helper(root, p, q):
p_left = self.cover(root.left, p)
q_left = self.cover(root.left, q)
if p_left != q_left:
return root
if p_left:
return helper(root.left, p, q)
else:
return helper(root.right, p, q)

return helper(root, p, q)
``````

The time is O(N) because it's n+ n1/2 + n1/4 + n*1/8...

• maybe you should leave

``````if self.cover(p, q):
return p
if self.cover(q, p):
return q
``````

outside the "lowestCommonAncestor", since when you recurse on node.left/ node.right
you are doing the cover again...I think it only needs to be checked once

here is the body of my lowestCommonAncester function, what we do is mostly the same
except that my cover(p,q) and cover(q,p) are only executed once

``````def lowestCommonAncestor(self, root, p, q):
if cover(p,q):
return p
if cover(q,p):
return q

def helper(node,x,y):
if node is None:
return None
if node is x or node is y:
return node
left = helper(node.left,x,y)      # you called lowestCommonAncestor, which will compyte cover(p,q) again
right = helper(node.right,x,y)
if left and right:
return node
if left:
return left
if right:
return right
return helper(root,p,q)``````

• I am not sure what you are talking about. I think my code is right. Can you modify it and submit your version to OJ? Then paste it here.

• I put up my code, please let me know if it make sense

• yes, you are right! I update my code.

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