Just walk down from the whole tree's root as long as both p and q are in the same subtree (meaning their values are both smaller or both larger than root's). This walks straight from the root to the LCA, not looking at the rest of the tree, so it's pretty much as fast as it gets. A few ways to do it:

**Iterative, O(1) space**

Python

```
def lowestCommonAncestor(self, root, p, q):
while (root.val - p.val) * (root.val - q.val) > 0:
root = (root.left, root.right)[p.val > root.val]
return root
```

Java

```
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
while ((root.val - p.val) * (root.val - q.val) > 0)
root = p.val < root.val ? root.left : root.right;
return root;
}
```

(in case of overflow, I'd do `(root.val - (long)p.val) * (root.val - (long)q.val)`

)

Different Python

```
def lowestCommonAncestor(self, root, p, q):
a, b = sorted([p.val, q.val])
while not a <= root.val <= b:
root = (root.left, root.right)[a > root.val]
return root
```

"Long" Python, maybe easiest to understand

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

**Recursive**

Python

```
def lowestCommonAncestor(self, root, p, q):
next = p.val < root.val > q.val and root.left or \
p.val > root.val < q.val and root.right
return self.lowestCommonAncestor(next, p, q) if next else root
```

Python One-Liner

```
def lowestCommonAncestor(self, root, p, q):
return root if (root.val - p.val) * (root.val - q.val) < 1 else \
self.lowestCommonAncestor((root.left, root.right)[p.val > root.val], p, q)
```

Java One-Liner

```
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
return (root.val - p.val) * (root.val - q.val) < 1 ? root :
lowestCommonAncestor(p.val < root.val ? root.left : root.right, p, q);
}
```

"Long" Python, maybe easiest to understand

```
def lowestCommonAncestor(self, root, p, q):
if p.val < root.val > q.val:
return self.lowestCommonAncestor(root.left, p, q)
if p.val > root.val < q.val:
return self.lowestCommonAncestor(root.right, p, q)
return root
```