# Explanation: LCA is the first root satisfying min(p,q) <= root <= max(p,q) in while loop

• Let me begin by stating the key fact:
LCA is the first root satisfying min(p,q) <= root <= max(p,q) in while loop

The key fact is simple, so is the code:

``````def lowestCommonAncestor(self, root, p, q):
while root:
if root.val < min(p.val, q.val):
root = root.right
elif root.val > max(p.val, q.val):
root = root.left
else:
return root
``````

Here is the explanation:

First, let's say we encounter root satisfying min(p,q) <= root <= max(p,q). This root is clearly common ancestor of both p and q due to BST property. Why this is the LOWEST common ancestor? Why root cannot go any deeper like root = root.left or root = root.right?

OK, if root goes to left further, root.left could still be common ancestor ONLY IF p and q are both on the left subtree of root due to ancestor requirement. It means p,q < root, which leads to a contradiction to min(p,q) <= root <= max(p,q).

Similarly, root cannot go to right further.

Life is short. Keep code neat.

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