Problem link ও উৎস
- **Original source:** Classic cross-topic capstone interview problem (LCA in a general binary tree)
- **Platform:** LeetCode —
- **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।
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
তোমাকে একটা binary tree আর তার ভেতরের দুটো node `p` ও `q` দেওয়া আছে। তোমার কাজ: এদের **lowest common ancestor (LCA)** খুঁজে বের করো — মানে এমন সবচেয়ে নিচের (root থেকে দূরতম) node, যার subtree-র ভেতরে `p` আর `q` **দুজনেই** আছে। (একটা node নিজের ancestor হতে পারে — তাই `p` যদি `q`-র ancestor হয়, উত্তর `p`-ই।)
```text
3
/ \
5 1
/ \
6 2 -> LCA(6, 2) = 5 (5-এর subtree-তেই দুজন আছে)
```
### Input ও output {#8-example-input-and-output}
ধরো গাছ `[3,5,1,6,2,0,8,null,null,7,4]`:
```text
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
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো একটা বিশাল বংশবৃক্ষ, আর তুমি দুজন আত্মীয়ের সবচেয়ে কাছের সাধারণ পূর্বপুরুষ খুঁজছ। তুমি একদম পাতা (নিচ) থেকে খবর ওপরে পাঠাচ্ছ: "এই শাখায় প্রথম জনকে পেয়েছি"। যেই পূর্বপুরুষের কাছে **দুই ভিন্ন শাখা থেকে** দুজনের খবর এসে মেলে — তিনিই সবচেয়ে কাছের সাধারণ পূর্বপুরুষ। তার ওপরের কেউও common, কিন্তু সে আর "lowest" নয়।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
এই 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।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic একটা **bottom-up meeting point**: প্রতিটা node নিচ থেকে একটা সংকেত পায় — "তোমার বাঁ subtree-তে কি `p` বা `q`-র কেউ পাওয়া গেছে? ডান subtree-তে?" তিনটে ঘটনা —
```text
- বাঁ আর ডান দুই দিক থেকেই কেউ পাওয়া গেল -> এই node-ই LCA (এখানেই দুই পথ মেলে)
- শুধু এক দিক থেকে পাওয়া গেল -> সেই দিকের উত্তরটাই উপরে পাঠাও
- কোনো দিকেই না, আর node নিজেও p/q নয় -> None পাঠাও
```
আর base: কোনো node যদি `None`, বা সে নিজেই `p` বা `q` হয় — তাকেই ফেরত পাঠাও (সে একটা "found" সংকেত)।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
বড় কোনো data structure লাগে না — শুধু **recursion**, যা প্রতিটা node থেকে হয় একটা found-node নয়তো `None` ফেরত পাঠায়। গাছটা 07 trees-এর node structure, আর নিচ থেকে উপরে উত্তর তোলা 06 recursion-এর post-order কাজ। implicit call-stack বাদে extra memory নেই।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
LCA-র সংজ্ঞাই **নিচ থেকে উপরের** — "কোন node-এ এসে দুই পথ প্রথমবার মেলে"। post-order recursion ঠিক এই দিকেই কাজ করে: child-দের উত্তর আগে আসে, তারপর parent সিদ্ধান্ত নেয় (06 recursion)। আর প্রতিটা subtree-র কাছ থেকে শুধু একটা সরল সংকেত (একটা node বা `None`) দরকার — কোনো list, set বা path store করতে হয় না। তাই tree + recursion-এর return value-ই যথেষ্ট, নিখুঁত ফিট।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: root থেকে `p` পর্যন্ত পুরো path বের করো, আর `q` পর্যন্ত পুরো path বের করো (দুটো node-list)। তারপর দুই path পাশাপাশি রেখে যতদূর তারা একই থাকে, সেই শেষ common node-ই LCA।
```text
path_p = root..p (list of nodes)
path_q = root..q
শেষ common node = যেখানে দুই path প্রথম আলাদা হয়, তার আগেরটা
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
এটা কাজ করে, কিন্তু দুটো আলাদা search করে দুটো পুরো path তৈরি করতে হয়, আর সেই দুই **list extra space**-এ রাখতে হয় (প্রতিটা O(h) পর্যন্ত)। দুবার গাছ ঘোরা + দুই list তুলনা — কাজ ও memory দুটোই বেশি। অথচ post-order recursion একই কাজ **এক পাসে, extra list ছাড়াই** করে — দুই child-এর সংকেত মিলিয়েই LCA ধরে ফেলে (06 recursion-এর সৌন্দর্য)।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: **LCA ঠিক সেই node, যার বাঁ subtree-তে একজন target আর ডান subtree-তে আরেকজন target পাওয়া যায়** (অথবা node নিজেই একজন target আর অন্যজন তার নিচে)। তাই প্রতিটা node থেকে শুধু একটা সংকেত উপরে পাঠালেই চলে — "আমার নিচে কোনো target আছে কি, থাকলে কোনটা" — আর প্রথম যে node দুই দিক থেকে সংকেত পায়, সে-ই উত্তর। এই observation দুই-path তুলনাকে এক-পাস recursion-এ নামায়।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
root থেকে recurse করো। base: node যদি `None`, বা `p`, বা `q` হয় — সেই node-ই ফেরত দাও (একটা found সংকেত)। নাহলে বাঁ ও ডান দুই child-এ recurse করো। দুই দিক থেকেই non-`None` ফিরলে — এই node-ই LCA, নিজেকে ফেরত দাও। শুধু এক দিক থেকে ফিরলে — সেই দিকের উত্তর উপরে পাঠাও (target বা পাওয়া-যাওয়া LCA, যেটাই হোক)। দুই দিকেই `None` হলে `None` পাঠাও। প্রতিটা node একবার ছোঁয়া — O(n)।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "দুই path বের করে তুলনা করব" ভাবার বদলে ভাবো "প্রতিটা node নিচ থেকে শুধু একটা সংকেত তোলে — আমার subtree-তে target আছে কি?" দুই subtree থেকে সংকেত যেখানে **একসাথে** আসে, সেই node-ই উত্তর। দুই-পাস path-building গলে যায় একটা post-order এক-পাসে।
### ছবিতে বোঝা {#7-visual-explanation}
`LCA(6, 4)` বের করি — found-সংকেত নিচ থেকে উপরে ওঠে:
```text
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-এ ধাপে ধাপে {#14-step-by-step-dry-run}
ছোট গাছ — root `3`, left `5`, right `1`; `LCA(5, 1)`:
1. `lca(3)`: `3` ≠ p,q → দুই child-এ যাও
2. `lca(5)`: `5 == p` → ফেরত দেয় node `5`
3. `lca(1)`: `1 == q` → ফেরত দেয় node `1`
4. `3`-এ ফিরে: বাঁ = `5` (non-None), ডান = `1` (non-None) → **দুই দিকেই** → `3`-ই LCA
5. return node `3`
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```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!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `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 মিলিয়ে দেখা {#17-output-walkthrough}
`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!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**O(n)** — সবচেয়ে খারাপ ক্ষেত্রে প্রতিটা node একবার ছোঁয়া হয় (দুই target দূরে থাকলে পুরো গাছ ঘুরতে হতে পারে), প্রতি touch O(1)।
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(h)** — recursion call-stack tree-র উচ্চতা `h`-র সমান (balanced হলে O(log n), skewed হলে O(n))। কোনো path-list বা extra structure লাগে না — brute force-এর তুলনায় এটাই সাশ্রয়।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- মান দিয়ে তুলনা (`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" আর "এক দিকে পেলে সেই দিক পাঠাও" — এই দুটো ঠিক রাখা জরুরি।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: binary tree-র উপর recursive traversal আর ancestor/subtree বোঝা (07 trees-এর [../../07-trees/](../../07-trees/README.md)) + post-order recursion, যেখানে parent তার সিদ্ধান্ত নেয় দুই child-এর return মিলিয়ে (06 recursion-এর [../../06-recursion-and-backtracking/](../../06-recursion-and-backtracking/README.md))। এই দুটো cold অবস্থায় জানা থাকলে post-order LCA নিজে থেকেই বেরিয়ে আসে।
### পরের অনুশীলন {#22-similar-harder-problems}
- Lowest Common Ancestor of a BST (BST হলে value compare করে এক দিকেই নামা যায়) —