Lowest Common Ancestor of a Binary Tree

Problem Link

Lowest Common Ancestor of a Binary Tree – LeetCode

Problem: Lowest Common Ancestor of a Binary Tree

Problem Statement

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

The lowest common ancestor is defined as:

"The lowest node in the tree that has both p and q as descendants (a node can be a descendant of itself)."

Examples

Example 1

        3
       / \
      5   1
     / \ / \
    6  2 0  8
      / \
     7   4

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1  
Output: 3

Example 2

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4  
Output: 5

Constraints

• The number of nodes in the tree is in the range [2, 10⁵]

• -10⁹ <= Node.val <= 10⁹

• All Node.val are unique

• p and q will exist in the tree

Intuition

We are given a binary tree (not necessarily a BST), so we must search both subtrees.

The key idea:

• Traverse the tree recursively.

• If we find either p or q, we return that node.

• If both left and right recursive calls return non-null, current node is the lowest common ancestor.

Approach (Recursive DFS)

Algorithm

1. Base Case: If root is null, or root == p or root == q, return root.

2. Recursively call LCA on the left and right subtree.

3. If both calls return non-null, current node is the LCA.

4. Else, return the non-null value among the left and right calls.

Code (Java)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
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 (left != null && right != null) {
            return root; // p and q found in different subtrees
        }

        return left != null ? left : right;
    }
}

Time and Space Complexity

• Time Complexity: O(N)
  Visit every node once in the worst case.

• Space Complexity: O(H)
  Due to recursive call stack, where H is the height of the tree.

Dry Run

Tree

        3
       / \
      5   1
     / \
    6   2
       / \
      7   4

Input: p = 5, q = 4

• Recursively traverse until 5 → found

• Traverse 5's subtree and find 4

• Since 5 contains both p and q, return 5

Conclusion

• This problem demonstrates post-order DFS traversal.

• The return path helps determine the LCA naturally.

• It works for any binary tree, not just BSTs.