Problem link ও উৎস
- **Original source:** Classic BST ancestor-search exercise
- **Platform:** LeetCode —
- **Topic:** trees
- **Difficulty:** Medium
- **Pattern:** BST property + LCA
- **Basic idea inherited from:** BST search, একসাথে দুটো target — split-point খোঁজা
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
তোমাকে একটা **Binary Search Tree** আর দুটো node `p` ও `q` দেওয়া আছে। তোমার কাজ: তাদের **lowest common ancestor (LCA)** বের করা — মানে সবচেয়ে গভীর সেই node যার subtree-তে `p` আর `q` দুজনেই আছে (একটা node নিজেও নিজের ancestor ধরা হয়)।
```text
6
/ \
2 8 LCA(2, 8) = 6 (একদিকে 2, অন্যদিকে 8)
/ \ / \
0 4 7 9 LCA(2, 4) = 2 (2 নিজেই 4-এর ancestor)
/ \
3 5
```
### Input ও output {#8-example-input-and-output}
```text
Input : root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output: 6
Input : root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
Output: 2 (2 নিজেই 4-এর ancestor)
Input : root = [6,2,8,0,4,7,9,null,null,3,5], p = 3, q = 5
Output: 4 (3 আর 5 দুজনেই 4-এর নিচে, আলাদা দিকে)
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
একটা পারিবারিক বংশলতিকা ভাবো যেখানে বাঁ দিকে ছোটরা, ডান দিকে বড়রা সাজানো (id দিয়ে)। দুজন আত্মীয়ের সবচেয়ে কাছের common পূর্বপুরুষ খুঁজতে শীর্ষ থেকে নামো: দুজনেই কোনো শাখার বাঁয়ে পড়লে সেই শাখায় নামো, দুজনেই ডানে পড়লে ডানে — যেখানে একজন এক দিকে আর আরেকজন অন্য দিকে, সেই ব্যক্তিই তাদের meeting point।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
এটা সরাসরি **BST search** থেকে আসে, কিন্তু একসাথে দুটো target নিয়ে। সাধারণ BST search-এ value-র সাথে তুলনা করে এক দিকে নামি। এখানে দুটো value নিয়ে নামি: দুটোই ছোট হলে বাঁয়ে, দুটোই বড় হলে ডানে। যেখানে তারা প্রথমবার আলাদা দিকে যায় (বা একটা current node-এর সমান হয়), সেটাই **fork** — মানে LCA।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic হলো ordering ব্যবহার করে fork খোঁজা:
```text
current node-এ দাঁড়িয়ে:
p.val আর q.val দুটোই < node.val → LCA বাঁয়ে
p.val আর q.val দুটোই > node.val → LCA ডানে
নাহলে (একটা ≤ node ≤ আরেকটা) → node-ই LCA (split point)
```
split point হলো প্রথম node যেখানে দুজনের path আলাদা হয় — BST-তে এটাই lowest common ancestor।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
কোনো extra data structure লাগে না। শুধু একটা **pointer** যা root থেকে শুরু করে নামে (iterative, O(1) extra space), অথবা **recursion call stack** (একই logic, recursive রূপে)।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
BST-র ordering প্রতিটা comparison-এ একটা পুরো subtree বাদ দিতে দেয়, তাই আমাদের শুধু একটা path-এ নামলেই হয় — কোনো queue বা stack লাগে না। একটা pointer-ই যথেষ্ট, কারণ আমরা কখনো ফিরে আসি না বা branch করি না; প্রতিটা ধাপে exactly এক দিকে নামি।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা (BST property ব্যবহার না করে): root থেকে p পর্যন্ত পুরো path বের করি, আর q পর্যন্ত পুরো path বের করি, তারপর দুই path-এ শেষ যে common node, সেটাই LCA।
```text
1) path to 2: [6, 2]
2) path to 8: [6, 8]
3) দুই path-এর শেষ common node = 6
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
এটা ঠিক উত্তর দেয়, কিন্তু দুটো আলাদা path বের করতে দুবার tree খোঁজা, আর সেই path-গুলো জমিয়ে রাখা — extra memory আর কাজ। BST-তে এর দরকারই নেই: ordering আমাদের একটা মাত্র downward walk-এ fork ধরিয়ে দেয়, কোনো path জমানো ছাড়াই।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: **BST-তে p আর q একসাথে current node-এর কোন দিকে পড়ে, সেটাই বলে দেয় কোথায় নামতে হবে।** যেই মুহূর্তে তারা আলাদা দিকে পড়ে (বা একটা current node হয়), সেই node-ই lowest common ancestor — আর নামার দরকার নেই।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
এটা একটা **guided downward walk** (BST search-এর জোড়া রূপ): root থেকে শুরু করো; দুটোই ছোট হলে বাঁয়ে, দুটোই বড় হলে ডানে; প্রথম যেখানে split (একটা ≤ node ≤ আরেকটা) সেখানেই উত্তর। মাত্র O(h) ধাপ — height-এর সমান, কারণ প্রতি ধাপে এক level নামি।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "দুটো path আলাদা করে বের করব" ভাবা বন্ধ করো। বরং ভাবো "দুজনকে একসাথে নিয়ে নামব, আর যেখানে তারা প্রথম আলাদা হয় সেখানেই থামব।" ordering-টাই তোমার কম্পাস — কোন দিকে নামতে হবে তা প্রতি node-এ একটাই comparison-এ বলে দেয়।
### ছবিতে বোঝা {#7-visual-explanation}
LCA(2, 8) খুঁজতে শীর্ষ থেকে নামার পথ:
```text
6 ← 2 < 6 আর 8 > 6 → split! এখানেই থামো
/ \
2 8
/ \ / \
0 4 7 9
2 বাঁয়ে, 8 ডানে → 6-ই fork → LCA = 6
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Input tree root 6, `p = 2`, `q = 8`:
1. node = 6। 2 < 6 কিন্তু 8 > 6 → একটা বাঁয়ে, একটা ডানে → **split!** node 6-ই LCA → return 6।
আরেকটা: `p = 3`, `q = 5` (দুজনেই 4-এর নিচে):
1. node = 6। 3 < 6 আর 5 < 6 → দুটোই বাঁয়ে → node = 2।
2. node = 2। 3 > 2 আর 5 > 2 → দুটোই ডানে → node = 4।
3. node = 4। 3 < 4 আর 5 > 4 → split → return 4।
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
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):
"""BST property দিয়ে value খুঁজে node ফেরত দেয় (test helper)।"""
node = root
while node:
if val < node.val:
node = node.left
elif val > node.val:
node = node.right
else:
return node
return None
def lca_bst(root, p, q):
node = root
while node:
if p.val < node.val and q.val < node.val: # দুটোই ছোট
node = node.left # বাঁয়ে নামো
elif p.val > node.val and q.val > node.val: # দুটোই বড়
node = node.right # ডানে নামো
else:
return node # split point = LCA
return None
# ---- tests ----
root = build_tree([6, 2, 8, 0, 4, 7, 9, None, None, 3, 5])
assert lca_bst(root, find(root, 2), find(root, 8)).val == 6
assert lca_bst(root, find(root, 2), find(root, 4)).val == 2
assert lca_bst(root, find(root, 3), find(root, 5)).val == 4
assert lca_bst(root, find(root, 0), find(root, 5)).val == 2
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `node = root` — root থেকে নামা শুরু।
- `if p.val < node.val and q.val < node.val: node = node.left` — দুজনেই ছোট, মানে দুজনেই বাঁ subtree-তে → বাঁয়ে নামো।
- `elif p.val > node.val and q.val > node.val: node = node.right` — দুজনেই বড় → ডানে নামো।
- `else: return node` — একজন এক দিকে আর আরেকজন অন্য দিকে (বা একজন current node) → এটাই split point, lowest common ancestor।
- `find` helper test-এর জন্য value থেকে node বের করে (BST search)।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`build_tree([6,2,8,0,4,7,9,None,None,3,5])` ওই BST বানায়; `lca_bst` LCA(2,8) = 6 ফেরত দেয় — assert pass। LCA(2,4) = 2 (একটা অন্যটার ancestor), LCA(3,5) = 4, LCA(0,5) = 2 — সব pass। শেষে print: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**O(h)** — root থেকে split point পর্যন্ত নামতে height h-এর সমান ধাপ। Balanced BST-তে O(log n), skewed-এ O(n)। দুবার tree খোঁজার brute force-এর চেয়ে কম।
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(1)** — iterative version শুধু একটা pointer রাখে, কোনো stack বা recursion ছাড়াই। (recursive লিখলে call stack-এর জন্য O(h) হতো।)
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- general binary tree-র postorder LCA এখানে লাগানো — ঠিক কাজ করবে কিন্তু BST-র সস্তা ordering-শর্টকাট মিস করবে (O(n) বনাম O(h))।
- "একটা node নিজের ancestor হতে পারে" কেস ভুলে যাওয়া — তখন p current node হলে split-শর্ত `else`-এ পড়ে, যা ঠিক।
- শুধু `<` / `>` ব্যবহার করতে গিয়ে সমান-কেস বাদ দেওয়া; `else` branch সেটা সামলায়।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: traversal-patterns.md-র Pattern D (LCA) আর Pattern C (BST property), সাথে BST search। ordering থাকায় path জমানোর দরকার নেই — একটা guided walk-ই fork ধরিয়ে দেয়।
### পরের অনুশীলন {#22-similar-harder-problems}
- LCA of a Binary Tree (ordering নেই, তাই postorder খোঁজা লাগে) —