LCA algorithm with a parent pointer and a set to save time

lca_parent_ptr_set.py

def find_lca(n1: BinaryTreeNode, n2: BinaryTreeNode) -> Optional[BinaryTreeNode]:
  seen_on_path: Set[BinaryTreeNode] = set()
    
  while n1 or n2:
    # go up the tree at the same time
    
    if n1:
      # at every point check if we have already seen the node
      if n1 in seen_on_path:
        # first seen will be an ancestor
        return n1
      seen_on_path.add(n1)
      n1 = n1.parent
    
    if n2:
      if n2 in seen_on_path:
        return n2
      seen_on_path.add(n2)
      n2 = n2.parent
  return None