LCA Code

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        '''
        Two takeaways:
        Takeaway 1
            Build solution by starting with trivial case.
            Then add a little bit more (1 more element).
            Continue growing and considering all cases until we reach a subproblem.
            
        Takeaway 2
            Really understand what the invariant (LCA) is.
            LCA Def'n
                LCA of a Null node is undefined.
                LCA where one element is the root
                    The root is by def'n the LCA.
                LCA where p and q are in DIFFERENT subtrees is the root.
                LCA will be found in EITHER the left or the right.
        '''
        # In an empty binary tree, there are no common ancestors.
        if root is None:
            return None

        # After the first Base Case, root cannot be None.
        
        # Root is EITHER p or q.
        if root is p or root is q:
            # This is the LCA because It is both p or q, AND the LCA.
            return root
        
        # root is NOT p AND NOT q.
        # LCA is definitely going to be entirely in the left or right subtree.
        left_lca = self.lowestCommonAncestor(root.left, p, q)
        right_lca = self.lowestCommonAncestor(root.right, p, q)
        
        # Case where p and q are found in different subtrees
        # Therefore, the root is the LCA
        if left_lca and right_lca:
            return root
        
        # p and q are both in the same subtree, therefore, the LCA is defined
        # only on the left or only on the right
        if not left_lca:
            return right_lca
        return left_lca