Problem link ও উৎস
- **Original source:** Classic cross-topic capstone interview problem (BST property checking)
- **Platform:** LeetCode —
- **Topic:** trees + recursion
- **Difficulty:** Medium
- **Pattern:** Range-passing recursion (valid-bounds propagation)
- **Basic idea inherited from:** এটা একটা cross-topic capstone — এখানে মেশে **07 trees** (একটা binary tree, BST-র property, node-এর left/right structure) আর **06 recursion** (প্রতিটা subtree-কে একই প্রশ্ন জিজ্ঞেস করা, সাথে একটা বৈধ range বহন করা)। দুই tool জোড়া লাগলেই range-passing validation।
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
তোমাকে একটা binary tree-র root দেওয়া আছে। তোমার কাজ: বলো এটা একটা **বৈধ Binary Search Tree (BST)** কিনা। BST-র নিয়ম: প্রতিটা node-এর জন্য — তার **পুরো left subtree**-র সব মান node-এর চেয়ে **ছোট**, আর তার **পুরো right subtree**-র সব মান node-এর চেয়ে **বড়** হতে হবে। শুধু `True`/`False` চাই।
```text
5
/ \
1 8 -> left(1) < 5 < right(8), দুই subtree-ও ঠিক -> True
```
### Input ও output {#8-example-input-and-output}
```text
Input : [2,1,3] -> Output: True # 1 < 2 < 3
Input : [5,1,4,null,null,3,6] -> Output: False # 4 root 5-এর ডানে, কিন্তু 4 < 5
Edge case 1 (একটা node): [1] -> Output: True
Edge case 2 (সমান মান): [2,2,2] -> Output: False # BST-তে duplicate (==) চলে না, strict <
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো একটা সাংগঠনিক চার্ট, যেখানে প্রতিটা পদের একটা "অনুমোদিত বেতন-পরিসর" আছে যা উপরের বসদের সিদ্ধান্ত থেকে নেমে আসে। তুমি ওপর থেকে নিচে নামছ — বাঁ শাখায় গেলে সর্বোচ্চ সীমা কমে (current বসের চেয়ে কম হতে হবে), ডান শাখায় গেলে সর্বনিম্ন সীমা বাড়ে। প্রতিটা পদের বেতন তার গড়িয়ে-আসা পরিসরের ভেতরে থাকতে হবে — একটাও বাইরে গেলে পুরো চার্ট অবৈধ।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
এই problem দুটো আগের chapter-এর tool জোড়া দেয়:
- **07 trees** থেকে: একটা binary tree-র উপর চলাফেরা — প্রতিটা node-এর `val`, `left`, `right`, আর BST-র অর্ডারিং property-টা কী মানে।
- **06 recursion** থেকে: একই প্রশ্নকে subtree-তে নামানো, আর সাথে একটা **অতিরিক্ত state** (এই node-এর মান কোন `(low, high)` range-এ থাকতে হবে) বহন করে নিচে পাঠানো।
একা tree-traversal তোমাকে দেয় সব node ছোঁয়ার ক্ষমতা; একা recursion দেয় বৈধ range নিচে passing করার ক্ষমতা। দুটো মিললে O(n) এক-পাস validation।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic একটা **range invariant**: শুধু "left child < node < right child" দেখা **যথেষ্ট নয়** — পুরো subtree জুড়ে নিয়ম ধরে রাখতে হয়। তাই প্রতিটা node-কে একটা বৈধ খোলা ব্যবধান `(low, high)` দিয়ে যাচাই করি — node-এর মান `low < val < high` হতে হবে। নিচে নামার সময় range সংকুচিত করি —
```text
left child -এ যাও: range হয় (low, node.val) -- এখন উপরের সীমা node.val
right child -এ যাও: range হয় (node.val, high) -- এখন নিচের সীমা node.val
```
root শুরু করে `(-inf, +inf)` দিয়ে। এই range নিচে গড়িয়ে গিয়ে ancestor-দের সব constraint একসাথে চাপায়।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
বড় কোনো data structure লাগে না — শুধু **recursion** আর প্রতিটা call-এ দুটো bound (`low`, `high`)। গাছটা 07 trees-এর node structure (`val/left/right`), আর range বহন করা 06 recursion-এর কাজ। implicit call-stack বাদে extra memory নেই।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
BST-র নিয়ম **recursive ভাবেই সংজ্ঞায়িত** — "বৈধ BST = root ঠিক range-এ + left subtree বৈধ + right subtree বৈধ"। এই self-similar কাঠামো recursion-এর সাথে নিখুঁত খাপ খায় (06 recursion)। আর প্রতিটা subtree-কে শুধু একটা সংকুচিত `(low, high)` জানালেই সেটা স্বয়ংসম্পূর্ণভাবে যাচাই হয় — কোনো global array বা extra structure লাগে না। তাই tree + দুটো bound-ই যথেষ্ট।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম (ভুল) সরল চিন্তা: প্রতিটা node-এ শুধু সরাসরি child-দের সাথে তুলনা করি — `left.val < node.val < right.val`। কিন্তু এটা subtree-গভীরে লুকোনো violation ধরে না।
একটা সঠিক brute force: প্রতিটা node-এর জন্য তার **পুরো** left subtree-র max আর right subtree-র min আলাদা করে বের করে তুলনা করা।
```text
def valid(node):
if node is None: return True
if max(left_subtree) >= node.val: return False
if min(right_subtree) <= node.val: return False
return valid(node.left) and valid(node.right)
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
ওই সঠিক brute force-এ প্রতিটা node-এর জন্য তার subtree-গুলোর min/max আলাদা করে পুরো ঘুরে বের করতে হয় — একই subtree বহুবার scan হয়। মোট প্রায় **O(n^2)** (skewed tree-তে)। মূল অপচয়: subtree-র সীমা বারবার নতুন করে গণনা — অথচ সেই সীমা ancestor থেকে একটা range হিসেবে নিচে passing করলে (06 recursion) এক পাসেই হয়ে যেত।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: **একটা node বৈধ কিনা তা শুধু তার নিজের child দেখে নয়, তার সব ancestor-এর চাপানো সীমার উপর নির্ভর করে** — আর সেই সব সীমা একটামাত্র `(low, high)` range-এ গুটিয়ে নিচে পাঠানো যায়। left-এ গেলে high কমে, right-এ গেলে low বাড়ে। এই একটা range বহন করলে প্রতিটা node ঠিক একবার দেখেই পুরো গাছ যাচাই — O(n)।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
root-কে `(-inf, +inf)` range দিয়ে শুরু করো। প্রতিটা node-এ চেক করো `low < val < high` — না মিললে সাথে সাথে `False`। মিললে দুই child-এ recurse করো সংকুচিত range সহ: left-কে `(low, val)`, right-কে `(val, high)`। সব node সফল হলে `True`। প্রতিটা node একবার ছোঁয়া হয়, প্রতি touch O(1) — তাই O(n)।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "প্রতিটা node-এ child-দের সাথে তুলনা করব" ভাবার বদলে ভাবো "প্রতিটা node একটা বৈধ পরিসর নিয়ে নামে — সে কি সেই পরিসরে আছে?" ancestor-দের সব constraint একটা `(low, high)`-তে গুটিয়ে নিলে গভীরে লুকোনো violation আপনিই ধরা পড়ে, এক পাসেই।
### ছবিতে বোঝা {#7-visual-explanation}
একটা **অবৈধ** গাছ দেখি — চোখে ঠিক মনে হলেও range ধরে ফেলে:
```text
5 range নিচে গড়ায়:
/ \
1 4 5 -> (-inf, +inf) 5 ঠিক
/ \ 1 -> (-inf, 5) 1 ঠিক
3 6 4 -> (5, +inf) 4 < 5 ? না! 4 > 5 লাগত
-> অবৈধ (4 আসলে 5-এর ডানে, তাই 5-এর চেয়ে বড় হতে হবে)
```
শুধু "4-এর child 3<4<6" দেখলে ভুল করে valid বলত; কিন্তু `4` তো `5`-এর right subtree-তে, তাই তাকে `5`-এর চেয়ে বড় হতেই হতো — range invariant সেটা ধরে।
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
`[2,1,3]` (root 2, left 1, right 3):
1. `check(2, -inf, +inf)`: `-inf < 2 < +inf` ✓ → দুই child-এ যাও
2. `check(1, -inf, 2)`: `-inf < 1 < 2` ✓ → child দুটো None → True
3. `check(3, 2, +inf)`: `2 < 3 < +inf` ✓ → child দুটো None → True
4. দুই subtree True → root True → return `True`
অবৈধ `[5,1,4,null,null,3,6]`: `check(4, 5, +inf)`-এ `5 < 4` মিথ্যা → সাথে সাথে `False`।
## কোড ও ব্যাখ্যা {#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 is_valid_bst(root):
def check(node, low, high):
if node is None:
return True # খালি subtree বৈধ
if not (low < node.val < high): # range-এর বাইরে?
return False
# left-এ high কমে, right-এ low বাড়ে
return check(node.left, low, node.val) and check(node.right, node.val, high)
return check(root, float('-inf'), float('inf'))
# ---- tests ----
# valid: [2,1,3]
assert is_valid_bst(TreeNode(2, TreeNode(1), TreeNode(3))) == True
# invalid: [5,1,4,null,null,3,6]
assert is_valid_bst(TreeNode(5, TreeNode(1),
TreeNode(4, TreeNode(3), TreeNode(6)))) == False
# single node
assert is_valid_bst(TreeNode(1)) == True
# empty tree
assert is_valid_bst(None) == True
# deep violation: [5,4,6,null,null,3,7] -> 3 in right subtree < 5
assert is_valid_bst(TreeNode(5, TreeNode(4),
TreeNode(6, TreeNode(3), TreeNode(7)))) == False
# equal values not allowed: [2,2,2]
assert is_valid_bst(TreeNode(2, TreeNode(2), TreeNode(2))) == False
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `class TreeNode` — স্ট্যান্ডার্ড binary-tree node (07 trees-এর `val/left/right`)।
- `def check(node, low, high)` — recursive helper; এই node-এর বৈধ পরিসর `(low, high)` বহন করে (06 recursion-এর extra state)।
- `if node is None: return True` — খালি subtree সবসময় বৈধ; recursion-এর base case।
- `if not (low < node.val < high): return False` — strict খোলা ব্যবধান চেক; সীমায় বসলেও (==) অবৈধ, তাই duplicate ধরা পড়ে।
- `check(node.left, low, node.val)` — left subtree-র সব মান current node-এর **চেয়ে ছোট** হতে হবে, তাই upper bound হয় `node.val`।
- `check(node.right, node.val, high)` — right subtree-র সব মান **চেয়ে বড়**, তাই lower bound হয় `node.val`।
- দুই recurse `and` — দুই subtree-ই বৈধ হলে তবেই node বৈধ।
- `return check(root, float('-inf'), float('inf'))` — root-এর উপর কোনো সীমা নেই, তাই অসীম range দিয়ে শুরু।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`[2,1,3]`-এ প্রতিটা node তার গড়িয়ে-আসা range-এ পড়ে — return True, assert pass। `[5,1,4,3,6]`-এ `4` node `(5, +inf)` range পায়, `5 < 4` মিথ্যা → False (যদিও `4`-এর নিজের child `3<4<6` ঠিক ছিল, range invariant deep violation ধরে)। `[2,2,2]`-এ `low < val < high` strict বলে সমান মান (`2 < 2` মিথ্যা) → False। খালি tree → True। শেষে print: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**O(n)** — প্রতিটা node ঠিক একবার ছোঁয়া হয়, প্রতি touch-এ O(1) range-চেক।
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(h)** — recursion call-stack tree-র উচ্চতা `h`-র সমান (balanced হলে O(log n), skewed হলে O(n))। কোনো অতিরিক্ত data structure নেই, শুধু stack।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- শুধু `node.left.val < node.val < node.right.val` চেক করা — deep violation ধরে না (যেমন `[5,4,6,3,7]`-এর `3`)। পুরো range বহন করতে হবে।
- `<=`/`>=` ব্যবহার করা strict `<`-এর বদলে — তখন সমান মান (duplicate) ভুল করে valid হয়; BST-তে সাধারণত strict।
- range-কে `node.val` দিয়ে update না করে অপরিবর্তিত পাঠানো — তাহলে ancestor constraint নিচে পৌঁছায় না।
- in-order traversal করে "sorted কিনা" দেখার সময় আগের মান `-inf` না রেখে ভুল init করা (বিকল্প পদ্ধতি; এখানে range-পদ্ধতিই সরল)।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: binary tree-র উপর recursive traversal আর BST-property বোঝা (07 trees-এর [../../07-trees/](../../07-trees/README.md)) + প্রতিটা recursive call-এ extra state (`low`, `high`) বহন করা (06 recursion-এর [../../06-recursion-and-backtracking/](../../06-recursion-and-backtracking/README.md))। এই দুটো cold অবস্থায় জানা থাকলে range-passing validation নিজে থেকেই বেরিয়ে আসে।
### পরের অনুশীলন {#22-similar-harder-problems}
- Recover Binary Search Tree (দুটো node ভুল জায়গায়, in-order দিয়ে তাদের খুঁজে swap) —