Problem link ও উৎস
- **Original source:** Classic BST property verification exercise
- **Platform:** LeetCode —
- **Topic:** trees
- **Difficulty:** Medium
- **Pattern:** BST bounds
- **Basic idea inherited from:** concept.md-র whole-subtree ফাঁদটা — property পুরো subtree-কে বাঁধে, শুধু সরাসরি child-কে না
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
তোমাকে একটা binary tree দেওয়া আছে। তোমার কাজ: যাচাই করা এটা সত্যিই একটা valid **Binary Search Tree (BST)** কিনা। নিয়ম: প্রতিটা node-এর জন্য তার পুরো **বাঁ subtree-র সব value তার চেয়ে ছোট**, আর পুরো **ডান subtree-র সব value তার চেয়ে বড়** (এই problem-এ duplicate allowed না)।
```text
5
/ \
3 8 ← valid: 3 < 5 < 8, আর নিচেও নিয়ম মানে
/ \ \
1 4 9
```
### Input ও output {#8-example-input-and-output}
```text
Input : root = [5,3,8,1,4,null,9]
Output: True
Input : root = [5,1,4,null,null,3,6]
Output: False (4-এর বাঁ subtree-তে 3 আছে, কিন্তু 3 < 5 — root নিয়ম ভাঙে)
Edge : root = [1] -> Output: True
Edge : root = [] -> Output: True (খালি tree vacuously valid)
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
একটা সংখ্যা-অনুমানের খেলা ভাবো যেখানে প্রতিটা প্রশ্নের পর তোমাকে বলা হয় "এখন তোমার উত্তর X আর Y-এর মাঝে হতে হবে।" বাঁয়ে গেলে উপরের সীমা কমে, ডানে গেলে নিচের সীমা বাড়ে। প্রতিটা node-কে এই ক্রমশ-সংকীর্ণ জানালার ভেতরে fit করতে হবে — না হলে tree-টা BST না।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
এটা concept.md-র সেই বিখ্যাত **whole-subtree ফাঁদ** থেকে আসে: BST নিয়ম শুধু "node > বাঁ child আর node < ডান child" না — পুরো বাঁ subtree আর পুরো ডান subtree-কে বাঁধে। তাই শুধু সরাসরি child দেখলে ভুল হয়; প্রতিটা node-কে তার ancestor-দের থেকে পাওয়া একটা **(low, high) range**-এ থাকতে হয়।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic হলো প্রতিটা node-এর জন্য একটা **valid interval** নিচে বহন করা:
```text
valid(node, low, high):
node is None হলে → True
low < node.val < high না হলে → False
valid(left, low, node.val) AND valid(right, node.val, high)
```
বাঁয়ে গেলে **ছাদ নামে** (high = node.val); ডানে গেলে **মেঝে ওঠে** (low = node.val)। root শুরু হয় (-∞, +∞) range-এ।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
কোনো extra data structure লাগে না। শুধু **recursion call stack**, আর প্রতিটা call-এর সাথে দুটো bound (`low`, `high`) নিচে পাঠানো। (বিকল্প: inorder traversal একটা list-এ দিয়ে strictly increasing কিনা দেখা।)
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
Tree self-similar, তাই recursion natural। আসল কায়দা: bound-গুলো call-এর argument হিসেবে নিচে বয়ে যায়, তাই প্রতিটা node জানে তার পূর্বপুরুষদের চাপানো সীমা কী। কোনো global state বা extra structure ছাড়াই পুরো subtree-র constraint একটা node-এ পৌঁছে যায়।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম (ভুল) সরল চিন্তা: প্রতিটা node-এ শুধু সরাসরি child চেক করি — `node.val > node.left.val` আর `node.val < node.right.val`।
```text
প্রতিটা node-এ:
left থাকলে: node.val > left.val ?
right থাকলে: node.val < right.val ?
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
এটা slow না — এটা **ভুল**। সরাসরি-child চেক একটা subtle case ধরে না: একটা node তার সরাসরি parent-এর তুলনায় ঠিক দিকে থাকতে পারে, কিন্তু কোনো দূরের ancestor-এর নিয়ম ভাঙতে পারে। যেমন root 5-এর ডান subtree-র গভীরে যদি 4 থাকে, সরাসরি-child চেক সেটা miss করে। তাই পুরো subtree-কে বাঁধতে bound নিচে পাঠানো লাগে।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: **প্রতিটা node তার সব ancestor-এর চাপানো একটা (low, high) interval-এ বাঁচে, শুধু তার সরাসরি parent-এর না।** বাঁয়ে নামলে high কমে আজকের node-এর value-তে; ডানে নামলে low বাড়ে। এই interval নিচে বহন করাই সঠিক উত্তরের চাবি।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
এটা একটা **bounded recursion** (একধরনের preorder check): প্রতিটা node-এ আগে নিজের range যাচাই করো, তারপর সংকুচিত range নিয়ে দুই দিকে নামো। বিকল্প হলো **inorder** traversal — BST-তে inorder strictly increasing হওয়া উচিত; কোথাও আগের মান ≥ পরের মান হলেই invalid। দুটোই O(n), একবার tree ঘোরা।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "প্রতিটা node-কে তার child-দের সাথে তুলনা করব" ভাবা বন্ধ করো — সেটাই বিখ্যাত ফাঁদ। বরং ভাবো "প্রতিটা node-কে একটা জানালা [low, high] দিয়ে নামব, আর নামার পথে জানালাটা সংকুচিত করব।" Constraint-টা parent থেকে child না, ancestor থেকে subtree।
### ছবিতে বোঝা {#7-visual-explanation}
প্রতিটা node-এর পাশে তার allowed (low, high) range; প্রতিটা মান ওই জানালায় ফিট করছে:
```text
5 (-inf, +inf)
/ \
(-inf, 5) 3 8 (5, +inf)
/ \ \
(-inf,3) 1 4 9 (8, +inf)
(3,5)
```
3 আছে (-∞,5)-এ ✓; 4 আছে (3,5)-এ ✓; 8 আছে (5,+∞)-এ ✓ — সব ফিট, valid।
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Invalid input `[5,1,4,null,null,3,6]` (root 5, ডান child 4, 4-এর বাঁ child 3):
1. `valid(5, -inf, +inf)` → 5 ঠিক। বাঁ: `valid(1, -inf, 5)`, ডান: `valid(4, 5, +inf)`।
2. `valid(1, -inf, 5)` → 1 ঠিক, child নেই → True।
3. `valid(4, 5, +inf)` → 4 < 5, কিন্তু range চায় `5 < 4` — **False**! (4 root 5-এর ডানে, তাই 4 > 5 হওয়া দরকার ছিল।)
4. একটা False পুরো উত্তরকে False করে দেয় → **False**।
## কোড ও ব্যাখ্যা {#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 is_valid_bst(node, low=float("-inf"), high=float("inf")):
if node is None: # খালি subtree সবসময় valid
return True
if not (low < node.val < high): # নিজের জানালায় ফিট করছে?
return False
# বাঁয়ে গেলে ছাদ নামে; ডানে গেলে মেঝে ওঠে
return (is_valid_bst(node.left, low, node.val) and
is_valid_bst(node.right, node.val, high))
# ---- tests ----
assert is_valid_bst(build_tree([5, 3, 8, 1, 4, None, 9])) is True
assert is_valid_bst(build_tree([5, 1, 4, None, None, 3, 6])) is False
assert is_valid_bst(build_tree([1])) is True
assert is_valid_bst(build_tree([])) is True
assert is_valid_bst(build_tree([2, 2, 2])) is False # duplicate, strict না
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `if node is None: return True` — খালি subtree vacuously valid।
- `if not (low < node.val < high): return False` — এই node তার ancestor-দের জানালায় ফিট না করলে invalid।
- `is_valid_bst(node.left, low, node.val)` — বাঁয়ে গেলে high নামে node-এর value-তে (বাঁ subtree-র সব এর চেয়ে ছোট হতে হবে)।
- `is_valid_bst(node.right, node.val, high)` — ডানে গেলে low ওঠে node-এর value-তে (ডান subtree-র সব এর চেয়ে বড় হতে হবে)।
- `and` — দুই দিকের যেকোনো একটা False হলেই পুরো subtree invalid।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`build_tree([5,3,8,1,4,None,9])` একটা সঠিক BST বানায়; `is_valid_bst` `True` ফেরত দেয় — assert pass। ফাঁদ-tree `[5,1,4,null,null,3,6]` ধরা পড়ে `False`, একক node `True`, খালি tree `True`, আর duplicate-যুক্ত `[2,2,2]` strict নিয়মে `False` — সব pass। শেষে print: `সব test pass!`।
### JavaScript ও test cases {#25-javascript-solution-with-test-cases}
```javascript
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;
}
// low/high জানালা নিচে বহন করি; বাঁয়ে গেলে ছাদ নামে, ডানে গেলে মেঝে ওঠে
function isValidBST(node, low = -Infinity, high = Infinity) {
if (node === null) return true; // খালি subtree সবসময় valid
if (!(low < node.val && node.val < high)) return false; // নিজের জানালায় ফিট?
return isValidBST(node.left, low, node.val)
&& isValidBST(node.right, node.val, high);
}
// ---- test cases ----
assert(isValidBST(buildTree([5, 3, 8, 1, 4, null, 9])) === true, "valid BST");
assert(isValidBST(buildTree([5, 1, 4, null, null, 3, 6])) === false, "ফাঁদ-tree");
assert(isValidBST(buildTree([1])) === true, "একক node");
assert(isValidBST(buildTree([])) === true, "খালি tree");
assert(isValidBST(buildTree([2, 2, 2])) === false, "duplicate, strict না");
console.log("সব JS test pass!");
```
> **JS টীকা:** Python-এর `float("-inf")`/`float("inf")`-এর সমতুল্য হলো JS-এর built-in `-Infinity`/`Infinity` — value যত বড়/ছোট হোক, root-এর initial জানালা কখনো ভাঙে না। লক্ষ্য করো Python-এর chained comparison `low < node.val < high` JS-এ সরাসরি কাজ করে না; তাই দুই অংশে ভেঙে `low < node.val && node.val < high` লিখতে হয়েছে — এটা একটা সাধারণ JS ফাঁদ।
### TypeScript ও test cases {#26-typescript-solution-with-test-cases}
```typescript
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 isValidBST(root: TreeNode | null, low: number = -Infinity, high: number = Infinity): boolean {
if (root === null) return true;
if (!(low < root.val && root.val < high)) return false;
return isValidBST(root.left, low, root.val) && isValidBST(root.right, root.val, high);
}
const expect = (cond: boolean, msg = ""): void => { if (!cond) throw new Error("FAIL " + msg); };
expect(isValidBST(buildTree([5, 3, 8, 1, 4, null, 9])) === true, "valid");
expect(isValidBST(buildTree([5, 1, 4, null, null, 3, 6])) === false, "invalid");
expect(isValidBST(buildTree([1])) === true, "একক");
expect(isValidBST(buildTree([])) === true, "খালি");
expect(isValidBST(buildTree([2, 2, 2])) === false, "dup");
console.log("সব TS test pass!");
```
> **TS টীকা:** `low: number` ও `high: number` typed হওয়ায় ভুল করে bound হিসেবে অন্য কিছু (string বা node) পাঠালে compile error — Python-এ এমন ভুল runtime পর্যন্ত লুকিয়ে থাকত। default value `-Infinity`/`Infinity` দিয়ে root call-এ শুধু `isValidBST(root)` লিখলেই চলে, type সঠিক থাকে।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**O(n)** — প্রতিটা node ঠিক একবার করে যাচাই হয় (n = node সংখ্যা)। এর চেয়ে কম সম্ভব না, কারণ একটা মাত্র ভুল node ধরতেও সবাইকে দেখতে হতে পারে।
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(h)** — recursion call stack tree-র height h সমান গভীর হয়। Balanced tree-তে O(log n), একপাশে-ঝোলা chain-এ O(n)।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- শুধু সরাসরি child-এর সাথে তুলনা করা (বিখ্যাত ভুল) — bound নিচে না পাঠালে দূরের ancestor-নিয়ম-ভাঙা ধরা পড়ে না।
- `<=` ব্যবহার করা যেখানে strict `<` দরকার (বা উল্টো) — duplicate নিয়ে problem-এর নিয়ম মন দিয়ে পড়ো।
- bound-এর জন্য int দিয়ে শুরু করা — value-গুলো বড়/ছোট হতে পারে, তাই `float("-inf")`/`float("inf")` নিরাপদ।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: traversal-patterns.md-র Pattern C (BST property exploitation) আর সেই "bounds নিচে পাঠাও" নিয়ম। concept.md-র whole-subtree ফাঁদ বুঝলেই কেন সরাসরি-child চেক যথেষ্ট না, তা পরিষ্কার হয়।
### পরের অনুশীলন {#22-similar-harder-problems}
- Kth Smallest Element in a BST (inorder = sorted property কাজে লাগাও) —