gumgum's Garden🌼

LCA in Binary Tree

Finding the lowest common ancestor of two nodes in a binary tree

def lca(root, node1, node2):
    ancestor = None
    def helper(root):
        nonlocal ancestor
        if root is None:
            return False
        left = helper(root.left)
        right = helper(root.right)
        if left and right:
            ancestor = root
            return True
        if root.val == node1.val or root.val == node2.val: 
            ancestor = root
            return True
        return left or right
    helper(root)

    if ancestor is None:
        print("No Ancestor")
    else:
        print(ancestor.val)
  • The target node could itself be the ancestor
  • The node which has node1 in left subtree and node2 in right subtree could also be the ancestor