lowest-common-ancestor-of-bst

Lowest Common Ancestor of Binary Search Tree

Solution 1: Recursion

pv, qv, rv = p.val, q.val, root.val
if pv < rv and qv < rv:
    return lowestCommonAncestor(root.left, p, q)
if pv > rv and qv > rv:
    return lowestCommonAncestor(root.right, p, q)
else:
    return root

Time and space complexity: $O(h)=O(n)$, worst case when tree is skewed and p, q are both leaves and siblings.

Solution 2: Iterative