Master DFS to Find the Lowest Common Ancestor (LCA) in a Binary Tree 🌲

🚀 Find the Lowest Common Ancestor (LCA) in a Binary Tree using DFS! 🌳

The Lowest Common Ancestor (LCA) of two nodes p and q is the deepest node in the tree that has both p and q as descendants. A node is also considered a descendant of itself.

🔹 💡 Understanding the Problem

Given a binary tree and two nodes p and q, we need to find their lowest common ancestor (LCA).
The LCA is the lowest node in the tree that has both p and q in its subtree.
A node can be an ancestor of itself.

💡 Example 1:

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

📌 Input: p = 5, q = 1
📌 Output: 3
📌 Explanation: The lowest common ancestor of 5 and 1 is 3, as 3 is the lowest node that has both 5 and 1 as descendants.

💡 Example 2:

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

📌 Input: p = 5, q = 4
📌 Output: 5
📌 Explanation: 5 is an ancestor of 4, so LCA = 5.

🔹 Approach: Recursive Depth-First Search (DFS)

We use recursive DFS traversal to find the LCA.

1️⃣ Base Case:

If root is None, return None (tree is empty).
If root == p or root == q, return root (we found one of the nodes).

2️⃣ Recursive Calls:

Recursively search for p and q in the left and right subtrees.

3️⃣ Decision Making:

If both left and right subtrees return non-null values, the current node is the LCA.
If only one subtree returns non-null, return that subtree’s result (it contains both p and q).

🔹 Python Solution (Recursive DFS)

class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right

class Solution:
def lowestCommonAncestor(self, root, p, q):
# Base case: If the current node is None, p, or q, return it
if not root or root == p or root == q:
return root

# Search for p and q in left and right subtrees
left = self.lowestCommonAncestor(root.left, p, q)
right = self.lowestCommonAncestor(root.right, p, q)

# If both left and right return non-null, current node is LCA
if left and right:
return root

# If only one side returns non-null, return that side
return left if left else right

🔹 Why This Approach Works Well?

✅ Recursive DFS ensures an efficient O(N) traversal.
✅ Handles all types of binary trees (balanced, skewed, full, etc.).
✅ Works without needing parent pointers or extra space.

⏳ Time Complexity: O(N), where N is the number of nodes.

📌 Space Complexity: O(H), where H is the height of the tree (recursive stack).

🔥 Master this fundamental problem to improve your tree traversal skills! 🚀

💡 #Python #DSA #BinaryTree #Recursion #Algorithm #CodingInterview #LeetCode #Programming