Lowest Common Ancestor: Recursive split Pattern

Learning Outcome

After this lesson, you should be able to use postorder recursion to bubble target matches upward and identify the first split point.

Problem Statement

Given a binary tree and two nodes p and q, return their lowest common ancestor. The lowest common ancestor is the lowest node that has both p and q as descendants, where a node can be a descendant of itself.

Brute Force Approach

Store the full path from the root to p and the full path from the root to q, then compare the paths to find the last common node.

This is understandable, but it uses extra path storage.

Optimized Approach

Use recursion. If the current node is null, p, or q, return it. Recurse left and right. If both sides return non-null, the current node is the LCA. Otherwise, bubble up whichever non-null side was found.

Exact Pseudocode

lca(node, p, q):
  if node is null or node is p or node is q:
    return node
  left = lca(node.left, p, q)
  right = lca(node.right, p, q)
  if left is not null and right is not null:
    return node
  if left is not null:
    return left
  return right
  

Reference Code

class Solution:
    def lowestCommonAncestor(self, root, p, q):
        if not root or root == p or root == q:
            return root

        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)

        if left and right:
            return root
        return left or right
  

Sample Dry Run

Complexity

Edge Cases

• One target is an ancestor of the other.
• Both targets are in the same subtree.
• Tree is skewed.

Interview Checklist

• Return immediately when the current node is p or q.
• If both left and right return non-null, current node is the LCA.
• Otherwise bubble up the non-null result.

FAQs

The common definition allows a node to be a descendant of itself, so if p is above q, p can be the LCA.

The current node needs to know what was found in both subtrees before deciding whether it is the split point.

Recursive split detection.