020 — Lowest Common Ancestor of a Binary Tree¶

অধ্যায় · সমস্ত অনুশীলন ও উৎস · ধাপে ধাপে শেখা

Problem link ও উৎস

Original source: Classic cross-topic capstone interview problem (LCA in a general binary tree)
Platform: LeetCode — https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/
Topic: trees + recursion
Difficulty: Medium
Pattern: Post-order reasoning (bubble-up found signals)
Basic idea inherited from: এটা একটা cross-topic capstone — এখানে মেশে 07 trees (একটা binary tree, ancestor/subtree-র ধারণা) আর 06 recursion (post-order — আগে দুই child-এর উত্তর নাও, তারপর নিজের সিদ্ধান্ত নাও)। দুই tool জোড়া লাগলেই post-order LCA।

প্রশ্ন ও উদাহরণ¶

সহজ করে প্রশ্ন¶

তোমাকে একটা binary tree আর তার ভেতরের দুটো node p ও q দেওয়া আছে। তোমার কাজ: এদের lowest common ancestor (LCA) খুঁজে বের করো — মানে এমন সবচেয়ে নিচের (root থেকে দূরতম) node, যার subtree-র ভেতরে p আর q দুজনেই আছে। (একটা node নিজের ancestor হতে পারে — তাই p যদি q-র ancestor হয়, উত্তর p-ই।)

উদাহরণ

       3
      / \
     5   1
    / \
   6   2     ->  LCA(6, 2) = 5    (5-এর subtree-তেই দুজন আছে)

Input ও output¶

ধরো গাছ [3,5,1,6,2,0,8,null,null,7,4]:

উদাহরণ

Input : p=5, q=1   -> Output: 3    # দুজন root-এর দুই পাশে
Input : p=5, q=4   -> Output: 5    # 5 নিজেই 4-এর ancestor

Edge case 1 (একজন অন্যের ancestor): p=5, q=6  -> Output: 5
Edge case 2 (দুজনই গভীরে এক পাশে): p=7, q=4   -> Output: 2

চেনা উদাহরণে বোঝা¶

ভাবো একটা বিশাল বংশবৃক্ষ, আর তুমি দুজন আত্মীয়ের সবচেয়ে কাছের সাধারণ পূর্বপুরুষ খুঁজছ। তুমি একদম পাতা (নিচ) থেকে খবর ওপরে পাঠাচ্ছ: "এই শাখায় প্রথম জনকে পেয়েছি"। যেই পূর্বপুরুষের কাছে দুই ভিন্ন শাখা থেকে দুজনের খবর এসে মেলে — তিনিই সবচেয়ে কাছের সাধারণ পূর্বপুরুষ। তার ওপরের কেউও common, কিন্তু সে আর "lowest" নয়।

ভিত্তির ধারণা¶

আগের কোন ধারণাটি লাগবে¶

এই problem দুটো আগের chapter-এর tool জোড়া দেয়:

07 trees থেকে: binary tree-র উপর চলাফেরা, ancestor/subtree মানে কী, কোন node কার নিচে পড়ে।
06 recursion থেকে: post-order চিন্তা — প্রতিটা node নিজের সিদ্ধান্ত নেওয়ার আগে আগে তার দুই child-এর কাছ থেকে উত্তর নেয়, তারপর সেই দুই উত্তর মিলিয়ে নিজে কী ফেরত পাঠাবে ঠিক করে।

একা tree-traversal তোমাকে দেয় সব node ছোঁয়ার ক্ষমতা; একা recursion দেয় নিচ থেকে উপরে তথ্য bubble-up করার ক্ষমতা। দুটো মিললে O(n) এক-পাস LCA।

ভেতরের যুক্তি¶

লুকানো logic একটা bottom-up meeting point: প্রতিটা node নিচ থেকে একটা সংকেত পায় — "তোমার বাঁ subtree-তে কি p বা q-র কেউ পাওয়া গেছে? ডান subtree-তে?" তিনটে ঘটনা —

উদাহরণ

- বাঁ আর ডান দুই দিক থেকেই কেউ পাওয়া গেল  -> এই node-ই LCA (এখানেই দুই পথ মেলে)
- শুধু এক দিক থেকে পাওয়া গেল             -> সেই দিকের উত্তরটাই উপরে পাঠাও
- কোনো দিকেই না, আর node নিজেও p/q নয়    -> None পাঠাও

আর base: কোনো node যদি None, বা সে নিজেই p বা q হয় — তাকেই ফেরত পাঠাও (সে একটা "found" সংকেত)।

কী দিয়ে তথ্য রাখব¶

বড় কোনো data structure লাগে না — শুধু recursion, যা প্রতিটা node থেকে হয় একটা found-node নয়তো None ফেরত পাঠায়। গাছটা 07 trees-এর node structure, আর নিচ থেকে উপরে উত্তর তোলা 06 recursion-এর post-order কাজ। implicit call-stack বাদে extra memory নেই।

এটি কেন উপযুক্ত¶

LCA-র সংজ্ঞাই নিচ থেকে উপরের — "কোন node-এ এসে দুই পথ প্রথমবার মেলে"। post-order recursion ঠিক এই দিকেই কাজ করে: child-দের উত্তর আগে আসে, তারপর parent সিদ্ধান্ত নেয় (06 recursion)। আর প্রতিটা subtree-র কাছ থেকে শুধু একটা সরল সংকেত (একটা node বা None) দরকার — কোনো list, set বা path store করতে হয় না। তাই tree + recursion-এর return value-ই যথেষ্ট, নিখুঁত ফিট।

ধাপে ধাপে সমাধান¶

প্রথম সরল উপায়¶

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

উদাহরণ

path_p = root..p  (list of nodes)
path_q = root..q
শেষ common node = যেখানে দুই path প্রথম আলাদা হয়, তার আগেরটা

কোথায় বেশি কাজ হচ্ছে¶

এটা কাজ করে, কিন্তু দুটো আলাদা search করে দুটো পুরো path তৈরি করতে হয়, আর সেই দুই list extra space-এ রাখতে হয় (প্রতিটা O(h) পর্যন্ত)। দুবার গাছ ঘোরা + দুই list তুলনা — কাজ ও memory দুটোই বেশি। অথচ post-order recursion একই কাজ এক পাসে, extra list ছাড়াই করে — দুই child-এর সংকেত মিলিয়েই LCA ধরে ফেলে (06 recursion-এর সৌন্দর্য)।

যে বিষয়টি খেয়াল করতে হবে¶

মূল observation: LCA ঠিক সেই node, যার বাঁ subtree-তে একজন target আর ডান subtree-তে আরেকজন target পাওয়া যায় (অথবা node নিজেই একজন target আর অন্যজন তার নিচে)। তাই প্রতিটা node থেকে শুধু একটা সংকেত উপরে পাঠালেই চলে — "আমার নিচে কোনো target আছে কি, থাকলে কোনটা" — আর প্রথম যে node দুই দিক থেকে সংকেত পায়, সে-ই উত্তর। এই observation দুই-path তুলনাকে এক-পাস recursion-এ নামায়।

আরও কম কাজে সমাধান¶

root থেকে recurse করো। base: node যদি None, বা p, বা q হয় — সেই node-ই ফেরত দাও (একটা found সংকেত)। নাহলে বাঁ ও ডান দুই child-এ recurse করো। দুই দিক থেকেই non-None ফিরলে — এই node-ই LCA, নিজেকে ফেরত দাও। শুধু এক দিক থেকে ফিরলে — সেই দিকের উত্তর উপরে পাঠাও (target বা পাওয়া-যাওয়া LCA, যেটাই হোক)। দুই দিকেই None হলে None পাঠাও। প্রতিটা node একবার ছোঁয়া — O(n)।

ভাবনার পরিবর্তন¶

মোচড়: "দুই path বের করে তুলনা করব" ভাবার বদলে ভাবো "প্রতিটা node নিচ থেকে শুধু একটা সংকেত তোলে — আমার subtree-তে target আছে কি?" দুই subtree থেকে সংকেত যেখানে একসাথে আসে, সেই node-ই উত্তর। দুই-পাস path-building গলে যায় একটা post-order এক-পাসে।

ছবিতে বোঝা¶

LCA(6, 4) বের করি — found-সংকেত নিচ থেকে উপরে ওঠে:

উদাহরণ

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

post-order bubble-up:
  6        -> "found 6"  (6 নিজেই target)
  7,4      -> 7:None ; 4:"found 4"
  2        -> বাঁ(7)=None, ডান(4)=found4  -> পাঠায় "found 4"
  5        -> বাঁ(6)=found6, ডান(2)=found4  -> দুই দিকেই!  5 = LCA
  3        -> বাঁ(5)=5(LCA), ডান(1)=None  -> পাঠায় 5 উপরে

উত্তর: 5

ছোট input-এ ধাপে ধাপে¶

ছোট গাছ — root 3, left 5, right 1; LCA(5, 1):

lca(3): 3 ≠ p,q → দুই child-এ যাও
lca(5): 5 == p → ফেরত দেয় node 5
lca(1): 1 == q → ফেরত দেয় node 1
3-এ ফিরে: বাঁ = 5 (non-None), ডান = 1 (non-None) → দুই দিকেই → 3-ই LCA
return node 3

কোড ও ব্যাখ্যা¶

Python¶

Python

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

def lowest_common_ancestor(root, p, q):
    # base: খালি, বা এই node-ই p/q -> এই node-ই found সংকেত
    if root is None or root is p or root is q:
        return root
    left = lowest_common_ancestor(root.left, p, q)
    right = lowest_common_ancestor(root.right, p, q)
    if left and right:        # দুই দিক থেকেই target -> এখানেই মেলে
        return root
    return left if left else right   # এক দিকের সংকেত উপরে পাঠাও

# ---- tests ----
#          3
#        /   \
#       5     1
#      / \   / \
#     6   2 0   8
#        / \
#       7   4
n7, n4 = TreeNode(7), TreeNode(4)
n6, n2 = TreeNode(6), TreeNode(2, n7, n4)
n0, n8 = TreeNode(0), TreeNode(8)
n5 = TreeNode(5, n6, n2)
n1 = TreeNode(1, n0, n8)
n3 = TreeNode(3, n5, n1)

assert lowest_common_ancestor(n3, n5, n1) is n3   # দুই পাশে
assert lowest_common_ancestor(n3, n5, n4) is n5   # 5 হলো 4-এর ancestor
assert lowest_common_ancestor(n3, n6, n4) is n5   # দুজনই 5-এর নিচে
assert lowest_common_ancestor(n3, n7, n8) is n3   # গভীর দুই পাশ
assert lowest_common_ancestor(n3, n6, n2) is n5   # 2, 6 দুজনই 5-এর child-দিকে
print("সব test pass!")

কোডের প্রতিটি অংশ¶

class TreeNode — স্ট্যান্ডার্ড binary-tree node (07 trees)।
if root is None or root is p or root is q: return root — তিনটে base: খালি subtree (None), বা এই node-ই একটা target — তখন সেই node-কেই "found" সংকেত হিসেবে উপরে পাঠাও। is দিয়ে identity তুলনা (মান না, আসল node)।
left = ...(root.left...) — বাঁ subtree-তে target খোঁজা (post-order: আগে নিচের উত্তর)।
right = ...(root.right...) — ডান subtree-তে target খোঁজা।
if left and right: return root — দুই দিক থেকেই non-None মানে দুই target দুই subtree-তে → এই node-ই lowest common ancestor।
return left if left else right — শুধু এক দিকে পাওয়া গেলে সেই উত্তর (target বা ইতিমধ্যে-পাওয়া LCA) উপরে পাঠাও; দুই দিকেই None হলে None যায়।

Output মিলিয়ে দেখা¶

LCA(5, 1)-এ 5 আর 1 root 3-এর দুই পাশে, তাই 3 দুই দিক থেকেই সংকেত পেয়ে নিজেকে ফেরত দেয় — return n3, assert pass। LCA(5, 4)-এ 5 node-এই base hit (root is p) হয়ে 5 উপরে ওঠে, আর 4-এর সংকেতও 5-এর subtree-তেই মেলে, তাই 5-ই LCA (একটা node নিজের ancestor)। LCA(7, 8)-এ 7 বাঁ-গভীরে, 8 ডান-গভীরে, প্রথম মেলা node 3। শেষে print: সব test pass!।

খরচ ও সাধারণ ভুল¶

সময়¶

O(n) — সবচেয়ে খারাপ ক্ষেত্রে প্রতিটা node একবার ছোঁয়া হয় (দুই target দূরে থাকলে পুরো গাছ ঘুরতে হতে পারে), প্রতি touch O(1)।

অতিরিক্ত জায়গা¶

O(h) — recursion call-stack tree-র উচ্চতা h-র সমান (balanced হলে O(log n), skewed হলে O(n))। কোনো path-list বা extra structure লাগে না — brute force-এর তুলনায় এটাই সাশ্রয়।

যে ভুলগুলো এড়াতে হবে¶

মান দিয়ে তুলনা (root.val == p.val) করা যখন গাছে duplicate মান থাকতে পারে — সঠিক node identity (is) দিয়ে তুলনা করো।
এটা BST ভেবে value-based shortcut নেওয়া — এটা সাধারণ binary tree, ordering নেই, তাই দুই subtree-ই দেখতে হবে।
base case-এ root is p or root is q ভুলে যাওয়া — তখন "একজন অন্যের ancestor" case ভাঙবে।
দুই subtree-র ফলাফল মেলানোর logic উল্টে ফেলা — "দুই দিকেই পেলে এই node" আর "এক দিকে পেলে সেই দিক পাঠাও" — এই দুটো ঠিক রাখা জরুরি।

শেখা ও পরের অনুশীলন¶

ভিত্তির সঙ্গে সম্পর্ক¶

ভিত্তি: binary tree-র উপর recursive traversal আর ancestor/subtree বোঝা (07 trees-এর ../../07-trees/) + post-order recursion, যেখানে parent তার সিদ্ধান্ত নেয় দুই child-এর return মিলিয়ে (06 recursion-এর ../../06-recursion-and-backtracking/)। এই দুটো cold অবস্থায় জানা থাকলে post-order LCA নিজে থেকেই বেরিয়ে আসে।

পরের অনুশীলন¶

Lowest Common Ancestor of a BST (BST হলে value compare করে এক দিকেই নামা যায়) — https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/
LCA III / with parent pointers (parent link থাকলে two-pointer chain) — https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree-iii/
Smallest Subtree with all the Deepest Nodes (একই post-order bubble-up, depth সহ) — https://leetcode.com/problems/smallest-subtree-with-all-the-deepest-nodes/

কৌশলটি মনে রাখুন¶

Post-order reasoning (bubble-up signals): প্রতিটা node তার দুই child-এর কাছ থেকে একটা সরল সংকেত (found-node বা None) নেয়, তারপর নিজে কী উপরে পাঠাবে ঠিক করে — দুই দিকে সংকেত মিললে সে-ই উত্তর। path-building ছাড়াই এক পাসে O(n)। trees + recursion combo-র canonical রূপ।

নিজেকে যাচাই করুন¶

ভবিষ্যতের আমাকে: "binary tree-তে দুটো node-এর LCA" দেখলেই post-order recursion মনে করবে — base-এ None/p/q হলে সেই node ফেরত দাও, দুই child-এ recurse করো, দুই দিকেই non-None ফিরলে এই node-ই LCA, নাহলে যে দিক থেকে এসেছে সেটা পাঠাও। সাধারণ tree-তে value নয়, node identity (is) দিয়ে তুলনা করো। trees-traversal আর post-order recursion-এর সবচেয়ে পরিষ্কার মেলবন্ধন।

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