Lowest Common Ancestor of a Binary Tree

Description

Lowest Common Ancestor of a Binary Tree

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

According to the definition of LCA on Wikipedia: “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 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.

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 a descendant of itself according to the LCA definition.

Example 3:
Input: root = [1,2], p = 1, q = 2
Output: 1

Constraints:

• The number of nodes in the tree is in the range [2, 105].
• -109 <= Node.val <= 109
• All Node.val are unique.
• p != q
• p and q will exist in the tree.

Approach 1: Recursive DFS ($O(N)$ Time, $O(H)$ Space)

Intuition

Traverse the binary tree using post-order DFS to find the target nodes p and q:

1. Base Case: If root == null, root == p, or root == q, return root.
2. Recursively search both subtrees: left = lowestCommonAncestor(root.left, p, q) and right = lowestCommonAncestor(root.right, p, q).
3. If both left and right return non-null, root is the Lowest Common Ancestor (since p and q reside in separate subtrees).
4. If only one subtree returns non-null, pass that non-null node upward (either both targets are in that branch or one target is an ancestor of the other).

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) {
            return root;
        }
 
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
 
        // If both left and right return non-null, current root is the LCA
        if (left != null && right != null) {
            return root;
        }
 
        // Return whichever branch found a node (or null if neither)
        return left != null ? left : right;
    }
}
 

Complexity

• Time Complexity: $O(N)$ — In the worst case, every node in the tree is visited once.
• Space Complexity: $O(H)$ — Max call stack size bounded by tree height $H$ ($O(\log N)$ for a balanced tree, $O(N)$ for a skewed tree).

---

Approach 2: Iterative BFS with Parent Mapping ($O(N)$ Time, $O(N)$ Space)

Intuition

Uses the standard level-order BFS template (ArrayDeque, queue.offer(), queue.poll()) to build parent pointers until both p and q are discovered:

1. Maintain a Map<TreeNode, TreeNode> to map each child node to its parent.
2. Run standard BFS starting from root until both p and q exist in parentMap.
3. Traverse up from p to root using parentMap, saving all of p’s ancestors in a Set<TreeNode>.
4. Traverse up from q. The first node encountered that exists in p’s ancestor set is the LCA.

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
 
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        Map<TreeNode, TreeNode> parentMap = new HashMap<>();
        Deque<TreeNode> queue = new ArrayDeque<>();
 
        parentMap.put(root, null);
        queue.offer(root);
 
        // Step 1: BFS to record parents until both p and q are found
        while (!parentMap.containsKey(p) || !parentMap.containsKey(q)) {
            TreeNode curr = queue.poll();
 
            if (curr.left != null) {
                parentMap.put(curr.left, curr);
                queue.offer(curr.left);
            }
            if (curr.right != null) {
                parentMap.put(curr.right, curr);
                queue.offer(curr.right);
            }
        }
 
        // Step 2: Collect all ancestors of node p
        Set<TreeNode> ancestors = new HashSet<>();
        TreeNode curr = p;
        while (curr != null) {
            ancestors.add(curr);
            curr = parentMap.get(curr);
        }
 
        // Step 3: Traverse up from q; first matching ancestor is LCA
        curr = q;
        while (!ancestors.contains(curr)) {
            curr = parentMap.get(curr);
        }
 
        return curr;
    }
}
 

Complexity

• Time Complexity: $O(N)$ — BFS visits nodes up to p and q, and ancestor traversal takes at most $O(H)$ time.
• Space Complexity: $O(N)$ — Extra memory needed for the BFS queue, parentMap, and ancestors set.

---

Easy Memory Rule

“DFS: If both left and right return non-null $\to$ root is LCA! $\to$ OR BFS: Build parentMap using Queue $\to$ find first common ancestor!”