lca.py

def lowestCommonAncestor(root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:

  def dfs(root: TreeNode) -> TreeNode:
        stack, found, ancestor = [], 0, None

        while root or stack:
            while root:
                stack.append((root, found))
                root = root.left

            root, had_already_found_one = stack.pop()

            found += root in [p,q]

            if found == 2:
                return ancestor if had_already_found_one else root
            elif not had_already_found_one and found == 1:
                ancestor = root

            root = root.right

    return dfs(root)