```
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+ n*1/2 + n*1/4 + n*1/8...