236. Lowest Common Ancestor of a Binary Tree

Solution 1: DFS

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if not root or (root == p or root == q):
            return root
        
        lcaOfLft = self.lowestCommonAncestor(root.left, p, q)
        lcaOfRht = self.lowestCommonAncestor(root.right, p, q)
        if lcaOfLft and lcaOfRht:
            return root
        elif lcaOfLft is None:
            return lcaOfRht
        else: # lcaOfRht is None:
            return lcaOfLft

Time Complexity: O(N)
Space Complexity: O(N) // Worst case happened when tree is skewed

Reference

https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/discuss/1405170/4-STEPS-SOLUTION-or-Easy-Heavily-EXPLAINED-with-COMPLEXITIES
https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/discuss/152682/Python-simple-recursive-solution-with-detailed-explanation