LeetCode 236. Lowest Common Ancestor of a Binary Tree

Intuition

Using recursive DFS, we want to find the correct left descendent and right descendent and handle each of the following 3 cases

1. If node is p or q, immediately return current node
2. If node receives both left and right child we found the lowest lowest common ancestor and return root
3. If found node from only one side, pass it up to parent

Optimal Solution

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':

        def dfs(root):
            if not root or root == p or root == q:
                return root
            left = dfs(root.left)
            right = dfs(root.right)

            if left and right:
                return root
            return left or right
        return dfs(root)

Time Complexity

O(N) Time Complexity

O(N) Space Complexity