Lowest Common Ancestor Algorithm with Parent Pointers

lca_parent_ptr.py

def find_lca(n1: BinaryTreeNode, n2: BinaryTreeNode) -> BinaryTreeNode:
  def get_depth(node: BinaryTreeNode) -> int:
    depth = 0
    while node and node.parent:
      node = node.parent
      depth += 1
    return depth
  
  d1 = get_depth(n1)
  d2 = get_depth(n2)
  
  while d1 > d2:
    n1 = n1.parent
    d1 -= 1
    
  while d2 > d1:
    n2 = n2.parent
    d2 -= 1
  
  while n1 != n2 and d1 > 0:
    d1 -= 1
    n1 = n1.parent
    n2 = n2.parent
  
  return n1