5.5 Lowest Common Ancestor (LCA)

Demo: Lowest Common Ancestor of a Binary Tree — LC 236 (Medium — Amazon/Facebook/Microsoft High)

Statement (Demo): binary tree-এর root এবং দুটো node p ও q দেওয়া — node দুটোর Lowest Common Ancestor (LCA) বের করুন। (LCA হলো এমন সর্বনিম্ন নোড যার subtree-তে p ও q উভয়ই অবস্থান করে।) উদাহরণ: root=[3,5,1,6,2,0,8], p=5, q=1 → node 3 | ⚡ n ≤ 10⁵, সব values unique

Approach: প্রতিটা নোড থেকে জিজ্ঞেস করুন — p বা q কি আমার subtree-তে? দুই পাশ থেকেই non-null ফেরত এলে এই নোডই LCA; এক পাশ থেকে এলে সেটাই উপরে পাঠান।

function lowestCommonAncestor(root, p, q) {
  if (!root || root === p || root === q) return root;
  const left = lowestCommonAncestor(root.left, p, q);
  const right = lowestCommonAncestor(root.right, p, q);
  if (left && right) return root; // দুই পাশে → এটাই LCA
  return left || right;
}

Complexity: Time O(n), Space O(h)