Lowest Common Ancestor

The lowest common ancestor (LCA) of two nodes is the deepest node that has both as descendants. A node can be a descendant of itself.

For nodes $p$ and $q$, three cases exist:

$1.$ Both in left subtree → LCA is in left

$2.$ Both in right subtree → LCA is in right

$3.$ One in each, or current node is $p$ or $q$ → current node is LCA

The recursive approach:

function lowestCommonAncestor(root, p, q):
    if root == null or root == p or root == q:
        return root
    left = lowestCommonAncestor(root.left, p, q)
    right = lowestCommonAncestor(root.right, p, q)
    if left and right:
        return root
    if left != null: return left
    return right

If both subtrees return non-null, current node is the LCA. Otherwise, return whichever subtree found something.