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