class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':

        if not root:
            return None

        # if either of them equals the root, root is the LCA
        if root == p or root == q:
            return root

        # if both lie to the left, explore left subtree
        if p.val < root.val and q.val < root.val:
            return self.lowestCommonAncestor(root.left, p, q)

        # if both lie to the right, explore right subtree
        if p.val > root.val and q.val > root.val:
            return self.lowestCommonAncestor(root.right, p, q)

        # if both lie on the either side of the root, then root is the lowest common ancestor
        return root