Leetcode 236. Lowest Common Ancestor of a Binary Tree

Problem

You are given the root of a binary tree along with two distinct node values p and q that are guaranteed to exist somewhere in the tree. Your task is to identify and return the value of the lowest common ancestor (LCA) of these two nodes.

The lowest common ancestor is defined as the node positioned deepest in the tree that has both p and q as descendants. Note that a node is considered a descendant of itself, meaning if one of the target values is an ancestor of the other, it serves as its own LCA.

Requirements

1. Return the value of the lowest common ancestor node
2. Handle cases where one target node is an ancestor of the other
3. Both target nodes are guaranteed to exist in the tree
4. All node values in the tree are unique

Constraints

• The number of nodes in the tree is in the range [2, 100000]
• -10^9 ≤= Node.val ≤= 10^9
• All Node.val are unique
• p != q
• p and q will exist in the tree

Examples

Example 1:

Input: 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 3. Node 3 is the root and both target nodes appear in different subtrees.

Example 2:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4 Output: 5 Explanation: The LCA of nodes 5 and 4 is 5 since a node can be an ancestor of itself. Node 4 is a descendant of node 5.

Example 3:

Input: root = [1,2], p = 1, q = 2 Output: 1 Explanation: In a simple two-node tree, the root is the LCA.

Hint 1: Recursive Exploration Think about how you can use recursion to explore both left and right subtrees. What information should each recursive call return to help determine if a subtree contains one or both target nodes?

Hint 2: Bottom-Up Approach Consider processing the tree from the leaves upward. When you find one of the target nodes, what should you pass back to the parent? What happens when a node receives positive signals from both its left and right children?

Hint 3: Key Decision Point The LCA is the first node (when traversing from leaves to root) where paths to both target nodes diverge. If you find one target in the left subtree and another in the right subtree, what does that tell you about the current node?

Full Solution `` Solution Explanation:

The algorithm uses a recursive depth-first search with three key observations:

1. Base Case: When we encounter a null node, we return null. When we find a node matching p or q, we return that node immediately.

2. Recursive Step: For each node, we recursively search both left and right subtrees. Each recursive call returns either:

   • null if neither target is found in that subtree
   • A target node if one is found
   • The LCA if both targets are found in that subtree

3. LCA Determination: A node becomes the LCA when:

   • Both left and right recursive calls return non-null values (meaning p is in one subtree and q is in the other)
   • OR the current node is one of the targets and the other target exists in one of its subtrees (handled by returning the node when we find a target)

Time Complexity: O(n) where n is the number of nodes in the tree. In the worst case, we visit every node exactly once.

Space Complexity: O(h) where h is the height of the tree, representing the maximum depth of the recursion stack. In the worst case (skewed tree), this could be O(n), but for a balanced tree, it's O(log n).

The beauty of this solution is that it elegantly handles all cases, including when one target is an ancestor of the other, by returning early when a target is found and trusting the recursive structure to propagate the correct answer upward.