LeetCode Solution 236 - Lowest Common Ancestor of a Binary Tree

Problem Statement

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

Definition of LCA: The lowest common ancestor is defined as the lowest node in the tree that has both nodes p and q as descendants (a node can be a descendant of itself).

Example 1:

Input:

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

p = 5, q = 1

Output:

3

Example 2:

Input:

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

p = 5, q = 4

Output:

5

---

Optimal Approach

We can solve this problem efficiently using Depth-First Search (DFS).

• If the root is null, return null.
• If the root is either p or q, return root.
• Recursively find p and q in left and right subtrees.
• If both left and right return non-null values, the current node is the LCA.
• Otherwise, return the non-null result from left or right.

Time Complexity:

• O(N), where N is the number of nodes in the tree (each node is visited once).

Space Complexity:

• O(H), where H is the height of the tree (recursion stack space).

---

LeetCode-Compatible C++ Solution

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (!root || root == p || root == q) return root;
        
        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);
        
        if (left && right) return root;
        return left ? left : right;
    }
};

---

Step-by-Step Explanation

1. Base Case: If root is NULL or matches p or q, return root.
2. Recursive Search: Call lowestCommonAncestor on left and right subtrees.
3. Processing Results:
   • If both left and right return non-null, root is the LCA.
   • Otherwise, return the non-null subtree (either left or right).

---

Dry Run Example

Input:

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

p = 5, q = 1

Execution Steps:

Step	Node	Left Result	Right Result	Return
1	3	5	1	3
2	5	6	2	5
3	1	0	8	1
4	6	NULL	NULL	NULL
5	2	7	4	2
6	0	NULL	NULL	NULL
7	8	NULL	NULL	NULL

Final LCA is 3.

---

Alternative Approaches & Why Not?

1. Storing Paths Approach (O(N) Space Complexity)

• Store paths to p and q.
• Compare both paths to find the first common node.
• Drawback: Extra space O(N) required.

2. Parent Pointers + HashSet (O(N) Space Complexity)

• Store all ancestors of p in a set.
• Traverse q’s ancestors and return the first match.
• Drawback: Requires additional data structures.

Approach	Time Complexity	Space Complexity
DFS (Best)	O(N)	O(H)
Storing Paths	O(N)	O(N)
HashSet + Parent Pointers	O(N)	O(N)

---

Conclusion

• Best Approach: Recursive DFS traversal with O(N) time and O(H) space.
• Why? Minimal extra space and efficient traversal.

Similar Problems to Practice:

• 🔗 Lowest Common Ancestor of a Binary Search Tree
• 🔗 Kth Ancestor of a Node in a Binary Tree
• 🔗 Deepest Leaves LCA

This solution ensures an efficient, LeetCode-compatible, and well-explained approach to solving the LCA problem. 🚀