Lowest Common Ancestor of a Binary Tree | Leetcode 236

Welcome to our deep dive on Lowest Common Ancestor of a Binary Tree (Leetcode 236). This problem is an elegant demonstration of Post-Order traversal to bubble information upwards.

Problem Statement

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).

Example: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 => Output: 3 (Explanation: The LCA of nodes 5 and 1 is logically the root 3.)

Approach: Recursive DFS (Bottom-Up) O(N)

We can search the tree recursively for p and q. We don't care about anything else. If we hit null, or if we hit p or q, we must immediately return that node straight back up!

The critical logic sits right below the recursive calls:

1. Search left: left = dfs(node.left)
2. Search right: right = dfs(node.right)
3. The Core Decision:
   • If both left and right returned non-null values, it means we found p on one side and q on the other! Therefore, the current node is intrinsically the LCA.
   • If only one side returned a non-null value, it means either p or q is located further down that single branch. Consequently, we bubble that non-null value upwards to the parent.
   • If both are null, return null.

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if not root or root == p or root == q:
            return root
            
        left_search = self.lowestCommonAncestor(root.left, p, q)
        right_search = self.lowestCommonAncestor(root.right, p, q)
        
        # If both are valid, the current node is the LCA!
        if left_search and right_search:
            return root
            
        # Otherwise, bubble up whatever is non-null
        return left_search if left_search else right_search

Complexity Analysis

Try it yourself!

Try this problem on LeetCode (236)