The recursive LCA works by searching both subtrees and combining results. Call lowestCommonAncestor on the left child and the right child. If both return a non-null node, the current node is the LCA because p and q are in different subtrees. If only one returns non-null, pass that result upward.
This is a post-order traversal. You process children before deciding about the current node. The algorithm visits each node once, giving time. Space is for the recursion stack, where is the tree height. For a balanced tree, . For a skewed tree, .