Implementation - LCA of a Binary Tree - Implement Solution

I will show you a recursive solution for the lowest common ancestor (LCA) in a binary tree. You return the node when you hit null or one of the targets. If both subtrees return a node, the current root is the LCA.

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

If only one subtree returns a node, you bubble that node up. This runs in $O(n)$ time and uses $O(h)$ space for the recursion stack.