017 — Lowest Common Ancestor of a Binary Tree¶

Source¶

Original source: Classic general-tree ancestor-search exercise
Platform: LeetCode — https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/
Topic: trees
Difficulty: Medium
Pattern: LCA (general, postorder)
Basic idea inherited from: LCA of BST, ordering সরিয়ে — এখন প্রতিটা subtree-কে জিজ্ঞেস করতে হয়

1. Problem in simple words¶

তোমাকে একটা সাধারণ binary tree (BST না — কোনো ordering নেই) আর দুটো node p ও q দেওয়া আছে। তোমার কাজ: তাদের lowest common ancestor (LCA) বের করা — সবচেয়ে গভীর সেই node যার subtree-তে দুজনেই আছে (একটা node নিজেও নিজের ancestor)।

        3
       / \
      5   1        LCA(5, 1) = 3   (একদিকে 5, অন্যদিকে 1)
     / \ / \
    6  2 0  8      LCA(5, 4) = 5   (4 হলো 5-এর subtree-তে)
      / \
     7   4

2. Which basic idea does this inherit from?¶

এটা LCA of BST (#16) থেকে আসে, কিন্তু ordering সরিয়ে নিলে। BST-তে value তুলনা করে এক দিকে নামা যেত; এখানে কোনো value-shortcut নেই, তাই প্রতিটা subtree-কে আলাদা করে জিজ্ঞেস করতে হয়: "তুমি কি p বা q পেয়েছ?" এটা একটা postorder কাজ — child-দের উত্তর থেকে node-এর সিদ্ধান্ত।

3. What is the hidden math or logic?¶

লুকানো logic হলো postorder-style "found-report":

search(node):
    node None হলে → None
    node p বা q হলে → node (পেয়েছি, উপরে জানাও)
    L = search(left),  R = search(right)
    L এবং R দুটোই non-None → এই node-ই LCA (এক করে এক দিকে পাওয়া গেছে)
    নাহলে → যেটা non-None সেটা উপরে পাঠাও (একটা found-signal)

যে node-এর দুই দিক থেকেই found-signal আসে, সেটাই split point — LCA।

4. Which data structure is needed?¶

কোনো extra data structure লাগে না। শুধু recursion call stack — প্রতিটা call নিচ থেকে একটা signal (None, বা একটা found node) উপরে ফেরত পাঠায়। tree-টাই data structure।

5. Why this data structure fits¶

Tree self-similar, আর এখানে আমাদের প্রতিটা subtree-র "ভেতরে p/q আছে কি" জানতে হয় — এটা ঠিক recursion-এর কাজ: প্রতিটা subtree নিজের উত্তর নিজে বের করে উপরে দেয়। postorder ক্রমে (child-আগে-parent) দুই দিকের signal একত্র করে node সিদ্ধান্ত নিতে পারে, কোনো extra structure ছাড়াই।

6. Real-life analogy¶

একটা বড় office-এ দুজন কর্মী p আর q হারিয়ে গেছে। প্রতিটা manager নিজের পুরো team-কে জিজ্ঞেস করে, "তোমাদের মধ্যে p বা q কেউ আছে?" Report নিচ থেকে উপরে আসে। যে manager-এর দুটো আলাদা sub-team থেকে আলাদা আলাদা করে দুজনের খবর আসে, সে-ই হলো দুজনের সবচেয়ে কাছের common boss — LCA।

7. Visual explanation¶

found-signal নিচ থেকে উপরে ওঠে; যে node দুই দিক থেকে signal পায়, সে-ই LCA:

        3   ← বাঁ থেকে 5-এর signal, ডান থেকে 1-এর signal → LCA = 3
       / \
   5(✓)   1(✓)
     / \ / \
    6  2 0  8
      / \
     7   4

LCA(5, 1): 5 বাঁয়ে পাওয়া গেল, 1 ডানে পাওয়া গেল → fork 3

8. Example input and output¶

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

Input : root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5     (4 হলো 5-এর subtree-তে, তাই 5 নিজেই ancestor)

Input : root = [3,5,1,...], p = 6, q = 4
Output: 5     (6 আর 4 দুজনেই 5-এর নিচে, আলাদা দিকে)

9. Brute force thinking¶

প্রথম সরল চিন্তা: root থেকে p পর্যন্ত পুরো path বের করি, আর q পর্যন্ত পুরো path বের করি (DFS দিয়ে), তারপর দুই path পাশাপাশি রেখে শেষ যে common node, সেটাই LCA।

1) path to 5: [3, 5]
2) path to 1: [3, 1]
3) দুই path মেলাও: শেষ common = 3

10. Why brute force is slow¶

এটা ঠিক উত্তর দেয় আর O(n)-ও, কিন্তু দুটো path আলাদা করে খুঁজতে দুবার tree ঘোরা, আর path দুটো জমিয়ে রাখা — extra memory আর pass। একটা single postorder traversal একবার ঘুরেই both target-এর signal উপরে তুলে fork ধরিয়ে দেয়, কোনো path list ছাড়াই।

11. Key observation¶

মূল observation: যে node-এর বাঁ subtree থেকে একটা target আর ডান subtree থেকে আরেকটা target পাওয়া যায়, সেই node-ই LCA। আর যদি দুটোই এক দিকে থাকে, তাহলে LCA সেই দিকেই আরো গভীরে — তাই non-None signal-টা শুধু উপরে পাঠিয়ে দিলেই চলে।

12. Optimized intuition¶

এটা একটা postorder found-report: প্রতিটা call তিনটার একটা ফেরত দেয় — None (এই subtree-তে কেউ নেই), বা p/q-র একটা (পেয়েছি), বা LCA। base-এ node p বা q হলে নিজেকে ফেরত দাও। দুই দিক থেকেই non-None এলে এই node LCA; নাহলে non-None-টা bubble up করো। একবার tree ঘোরা — O(n)।

13. Thinking tweak¶

মোচড়: BST-র মতো "কোন দিকে নামব" ভাবা বন্ধ করো — ordering নেই, তাই আগে থেকে দিক জানা যায় না। বরং ভাবো "প্রতিটা subtree-কে জিজ্ঞেস করব সে কী পেয়েছে, তারপর নিচ থেকে আসা উত্তর মিলিয়ে সিদ্ধান্ত নেব।" সিদ্ধান্তটা top-down না, bottom-up।

14. Step-by-step dry run¶

Input root 3, p = 5, q = 1:

search(3) → বাঁ আর ডান লাগবে।
search(5): 5 == p → 5 ফেরত (found-signal)।
search(1): 1 == q → 1 ফেরত (found-signal)।
node 3-এ: L = 5 (non-None), R = 1 (non-None) → দুই দিকেই পাওয়া গেছে → LCA = 3, return 3।

আরেকটা: p = 6, q = 4 (দুজনেই 5-এর নিচে):

node 3: L = search(5), R = search(1) = None।
search(5): L = search(6) = 6, R = search(2) → 2-এর ডানে 4 পাওয়া যায় = 4। দুই দিকেই non-None → LCA = 5।
node 3-এ: L = 5, R = None → non-None (5) bubble up → final 5।

15. Python solution¶

from collections import deque


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


def build_tree(values):
    """level-order list (None = missing child) থেকে tree বানায়।"""
    if not values:
        return None
    root = TreeNode(values[0])
    q = deque([root])
    i = 1
    while q and i < len(values):
        node = q.popleft()
        if i < len(values) and values[i] is not None:
            node.left = TreeNode(values[i])
            q.append(node.left)
        i += 1
        if i < len(values) and values[i] is not None:
            node.right = TreeNode(values[i])
            q.append(node.right)
        i += 1
    return root


def find(root, val):
    """value থেকে node বের করে (general tree, BFS) — test helper।"""
    if root is None:
        return None
    q = deque([root])
    while q:
        node = q.popleft()
        if node.val == val:
            return node
        if node.left:
            q.append(node.left)
        if node.right:
            q.append(node.right)
    return None


def lca(node, p, q):
    if node is None:                 # খালি subtree: কেউ নেই
        return None
    if node is p or node is q:       # p বা q পেয়ে গেছি, উপরে জানাও
        return node
    left = lca(node.left, p, q)      # বাঁ subtree কী পেল?
    right = lca(node.right, p, q)    # ডান subtree কী পেল?
    if left and right:               # দুই দিকেই পাওয়া গেছে
        return node                  # এই node-ই split point = LCA
    return left if left else right   # নাহলে যেটা non-None সেটা bubble up


# ---- tests ----
root = build_tree([3, 5, 1, 6, 2, 0, 8, None, None, 7, 4])
assert lca(root, find(root, 5), find(root, 1)).val == 3
assert lca(root, find(root, 5), find(root, 4)).val == 5
assert lca(root, find(root, 6), find(root, 4)).val == 5
assert lca(root, find(root, 7), find(root, 8)).val == 3
print("সব test pass!")

16. Line-by-line code explanation¶

if node is None: return None — খালি subtree-তে কেউ নেই, কোনো signal না।
if node is p or node is q: return node — p বা q-তে পৌঁছেছি, এই found-signal উপরে দাও।
left = lca(node.left, p, q) / right = lca(node.right, p, q) — দুই subtree-কে জিজ্ঞেস করো তারা কী পেল।
if left and right: return node — বাঁ দিক থেকে একজন, ডান দিক থেকে আরেকজন → এই node-ই LCA।
return left if left else right — শুধু এক দিকে পাওয়া গেলে সেই non-None signal উপরে bubble up করো।

17. Output walkthrough¶

build_tree([3,5,1,6,2,0,8,None,None,7,4]) ওই tree বানায়; lca LCA(5,1) = 3 ফেরত দেয় — assert pass। LCA(5,4) = 5 (একটা অন্যটার ancestor), LCA(6,4) = 5, LCA(7,8) = 3 — সব pass। শেষে print: সব test pass!।

18. Time complexity¶

O(n) — প্রতিটা node ঠিক একবার করে visit হয় (n = node সংখ্যা)। ordering নেই বলে আগে থেকে কোনো subtree বাদ দেওয়া যায় না, তাই সবাইকে দেখতে হতে পারে।

19. Space complexity¶

O(h) — recursion call stack tree-র height h সমান গভীর হয়। Balanced tree-তে O(log n), skewed chain-এ O(n)।

20. Common mistakes¶

value তুলনা করে BST-র মতো এক দিকে নামার চেষ্টা — general tree-তে ordering নেই, তাই কাজ করবে না।
"node নিজেও নিজের ancestor" base case বাদ দেওয়া — তখন p, q-র একজন অন্যজনের ancestor হলে ভুল উত্তর।
left and right চেক না করে শুধু একটা দিকের উপর নির্ভর করা — তখন fork-node মিস হয়।

21. Which basic problem this inherits from¶

ভিত্তি: LCA of BST (#16)-এর fork ধারণা, কিন্তু ordering-শর্টকাট বাদ; আর traversal-patterns.md-র Pattern D (LCA, general)। "প্রতিটা subtree-কে জিজ্ঞেস করো"-টাই এখানকার মূল।

22. Similar harder problems¶

Binary Tree Maximum Path Sum (একই bottom-up bend, value সহ) — https://leetcode.com/problems/binary-tree-maximum-path-sum/ (এই tracker-এর #23)
Lowest Common Ancestor of a Binary Tree II (p/q থাকতেও পারে, নাও পারে) — https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree-ii/
Smallest Subtree with all the Deepest Nodes (একই found-bubble কাঠামো) — https://leetcode.com/problems/smallest-subtree-with-all-the-deepest-nodes/

23. Pattern learned¶

Postorder found-report: যখন কোনো ordering নেই কিন্তু "দুটো node-এর সম্পর্ক" জানতে হয়, প্রতিটা subtree-কে একটা signal উপরে পাঠাতে দাও; দুই দিক থেকে signal এলে current node-ই উত্তর, নাহলে non-None bubble up করো। General-tree LCA হলো এর আদর্শ রূপ।

24. Final summary¶

ভবিষ্যতের আমাকে: "general tree-তে LCA = postorder; দুই দিক থেকে found এলে এই node, নাহলে যেটা পাওয়া গেছে সেটা উপরে দাও।" BST-র ordering-শর্টকাট এখানে নেই, তাই সবাইকে জিজ্ঞেস করতে হয় — O(n)। 'ordering ছাড়া দুটো node-এর meeting point' দেখলেই এই bottom-up found-report মনে করবে।

25. JavaScript solution (with test cases)¶

const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };

class TreeNode {
  constructor(val = 0, left = null, right = null) {
    this.val = val; this.left = left; this.right = right;
  }
}

function buildTree(values) {
  if (!values || values.length === 0) return null;
  const root = new TreeNode(values[0]);
  const q = [root];
  let i = 1, head = 0;
  while (head < q.length && i < values.length) {
    const node = q[head++];
    if (i < values.length && values[i] !== null) { node.left = new TreeNode(values[i]); q.push(node.left); }
    i++;
    if (i < values.length && values[i] !== null) { node.right = new TreeNode(values[i]); q.push(node.right); }
    i++;
  }
  return root;
}

// value থেকে node বের করে (general tree, BFS) — test helper
function find(root, val) {
  if (root === null) return null;
  const q = [root];
  let head = 0;
  while (head < q.length) {
    const node = q[head++];
    if (node.val === val) return node;
    if (node.left) q.push(node.left);
    if (node.right) q.push(node.right);
  }
  return null;
}

function lca(node, p, q) {
  if (node === null) return null;            // খালি subtree: কেউ নেই
  if (node === p || node === q) return node; // p বা q পেয়ে গেছি, উপরে জানাও
  const left = lca(node.left, p, q);         // বাঁ subtree কী পেল?
  const right = lca(node.right, p, q);       // ডান subtree কী পেল?
  if (left && right) return node;            // দুই দিকেই পাওয়া গেছে → এই node-ই LCA
  return left ? left : right;                // নাহলে যেটা non-null সেটা bubble up
}

// ---- test cases ----
const root = buildTree([3, 5, 1, 6, 2, 0, 8, null, null, 7, 4]);
assert(lca(root, find(root, 5), find(root, 1)).val === 3, "LCA(5,1)=3");
assert(lca(root, find(root, 5), find(root, 4)).val === 5, "LCA(5,4)=5");
assert(lca(root, find(root, 6), find(root, 4)).val === 5, "LCA(6,4)=5");
assert(lca(root, find(root, 7), find(root, 8)).val === 3, "LCA(7,8)=3");
console.log("সব JS test pass!");

JS টীকা: Python-এর identity তুলনা node is p (একই object কিনা) JS-এ হয় node === p — object-এর জন্য === reference সমতা দেখে, value নয়, ঠিক যা এখানে দরকার। মনে রেখো node.val === val (value) আর node === p (object) দুটো আলাদা; এখানে দুটোই ব্যবহৃত হয়েছে আলাদা উদ্দেশ্যে।

26. TypeScript solution (with test cases)¶

interface TreeNode { val: number; left: TreeNode | null; right: TreeNode | null; }

function node(val: number, left: TreeNode | null = null, right: TreeNode | null = null): TreeNode {
  return { val, left, right };
}

function buildTree(values: (number | null)[]): TreeNode | null {
  if (values.length === 0) return null;
  const root = node(values[0] as number);
  const q: TreeNode[] = [root];
  let i = 1, head = 0;
  while (head < q.length && i < values.length) {
    const cur = q[head++];
    if (i < values.length && values[i] !== null) { cur.left = node(values[i] as number); q.push(cur.left); }
    i++;
    if (i < values.length && values[i] !== null) { cur.right = node(values[i] as number); q.push(cur.right); }
    i++;
  }
  return root;
}

function find(root: TreeNode | null, val: number): TreeNode | null {
  if (root === null) return null;
  const q: TreeNode[] = [root];
  let head = 0;
  while (head < q.length) {
    const cur = q[head++];
    if (cur.val === val) return cur;
    if (cur.left) q.push(cur.left);
    if (cur.right) q.push(cur.right);
  }
  return null;
}

function lca(node: TreeNode | null, p: TreeNode, q: TreeNode): TreeNode | null {
  if (node === null) return null;
  if (node === p || node === q) return node;
  const left = lca(node.left, p, q);
  const right = lca(node.right, p, q);
  if (left && right) return node;
  return left ? left : right;
}

const expect = (cond: boolean, msg = ""): void => { if (!cond) throw new Error("FAIL " + msg); };
const root = buildTree([3, 5, 1, 6, 2, 0, 8, null, null, 7, 4]);

expect(lca(root, find(root, 5)!, find(root, 1)!)!.val === 3, "3");
expect(lca(root, find(root, 5)!, find(root, 4)!)!.val === 5, "5a");
expect(lca(root, find(root, 6)!, find(root, 4)!)!.val === 5, "5b");
expect(lca(root, find(root, 7)!, find(root, 8)!)!.val === 3, "3b");
console.log("সব TS test pass!");

TS টীকা: find ফেরত দেয় TreeNode | null, কিন্তু lca-র প্যারামিটার p: TreeNode (non-null) চায় — তাই test-এ find(...)! দিয়ে non-null assertion দিই (আমরা জানি এই value-গুলো tree-তে আছে)। শেষে .val-এর আগেও ! লাগে, কারণ lca-র return type TreeNode | null। এই !-গুলোই compiler-কে দিয়ে স্পষ্ট করায় কোথায় আমরা "এটা null না" নিশ্চিত।

27. কোথায় কাজে লাগে (real-world use)¶

File system common ancestor: দুটো ফাইল/folder-এর সবচেয়ে কাছের common parent directory বের করা — relative path হিসাব বা shared permission নির্ণয়ে।
Version control (git merge base): দুই branch-এর সর্বশেষ common commit (merge base) খোঁজা মূলত একটা LCA সমস্যা।
Org hierarchy: দুজন কর্মীর সবচেয়ে নিচু common manager বের করা — approval routing বা responsibility নির্ধারণে।
Taxonomy / category tree: দুটো ক্যাটাগরির common ancestor category বের করা — e-commerce-এ "related products" বা breadcrumb-এ।
XML/DOM manipulation: দুটো DOM node-এর nearest common ancestor element খোঁজা — event delegation বা range selection-এ ব্যবহৃত হয়।

মূল সুর: কোনো hierarchy-তে "এই দুটো জিনিসের সবচেয়ে কাছের common parent কে?" — এই প্রশ্ন এলেই bottom-up found-report (postorder) LCA-র কথা ভাববে।

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" দাবি নেই — এটা একটা common interview pattern।