014 — Validate Binary Search Tree¶

Source¶

Original source: Classic BST property verification exercise
Platform: LeetCode — https://leetcode.com/problems/validate-binary-search-tree/
Topic: trees
Difficulty: Medium
Pattern: BST bounds
Basic idea inherited from: concept.md-র whole-subtree ফাঁদটা — property পুরো subtree-কে বাঁধে, শুধু সরাসরি child-কে না

1. Problem in simple words¶

তোমাকে একটা binary tree দেওয়া আছে। তোমার কাজ: যাচাই করা এটা সত্যিই একটা valid Binary Search Tree (BST) কিনা। নিয়ম: প্রতিটা node-এর জন্য তার পুরো বাঁ subtree-র সব value তার চেয়ে ছোট, আর পুরো ডান subtree-র সব value তার চেয়ে বড় (এই problem-এ duplicate allowed না)।

        5
       / \
      3   8        ← valid: 3 < 5 < 8, আর নিচেও নিয়ম মানে
     / \   \
    1   4   9

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 নিচে বহন করা:

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-এ পৌঁছে যায়।

6. Real-life analogy¶

একটা সংখ্যা-অনুমানের খেলা ভাবো যেখানে প্রতিটা প্রশ্নের পর তোমাকে বলা হয় "এখন তোমার উত্তর X আর Y-এর মাঝে হতে হবে।" বাঁয়ে গেলে উপরের সীমা কমে, ডানে গেলে নিচের সীমা বাড়ে। প্রতিটা node-কে এই ক্রমশ-সংকীর্ণ জানালার ভেতরে fit করতে হবে — না হলে tree-টা BST না।

7. Visual explanation¶

প্রতিটা node-এর পাশে তার allowed (low, high) range; প্রতিটা মান ওই জানালায় ফিট করছে:

              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।

8. Example input and output¶

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)

9. Brute force thinking¶

প্রথম (ভুল) সরল চিন্তা: প্রতিটা node-এ শুধু সরাসরি child চেক করি — node.val > node.left.val আর node.val < node.right.val।

প্রতিটা 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।

14. Step-by-step dry run¶

Invalid input [5,1,4,null,null,3,6] (root 5, ডান child 4, 4-এর বাঁ child 3):

valid(5, -inf, +inf) → 5 ঠিক। বাঁ: valid(1, -inf, 5), ডান: valid(4, 5, +inf)।
valid(1, -inf, 5) → 1 ঠিক, child নেই → True।
valid(4, 5, +inf) → 4 < 5, কিন্তু range চায় 5 < 4 — False! (4 root 5-এর ডানে, তাই 4 > 5 হওয়া দরকার ছিল।)
একটা False পুরো উত্তরকে False করে দেয় → False।

15. Python solution¶

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।

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!।

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") নিরাপদ।

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 কাজে লাগাও) — https://leetcode.com/problems/kth-smallest-element-in-a-bst/ (এই tracker-এর #15)
Recover Binary Search Tree (দুটো swap হওয়া node খুঁজে ঠিক করো) — https://leetcode.com/problems/recover-binary-search-tree/
Convert Sorted Array to Binary Search Tree (উল্টো দিকে — sorted থেকে BST) — https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/

23. Pattern learned¶

Bounds-passing validation: যখন কোনো property পুরো subtree-কে বাঁধে (শুধু সরাসরি child-কে না), constraint-টা recursion-এর argument হিসেবে নিচে বহন করো আর প্রতি ধাপে সংকুচিত করো। BST validation হলো এর আদর্শ রূপ — interval নিচে নামে, প্রতিটা node তার জানালায় ফিট করে।

24. Final summary¶

ভবিষ্যতের আমাকে: "valid BST = প্রতিটা node তার (low, high) জানালায় ফিট, বাঁয়ে ছাদ নামে, ডানে মেঝে ওঠে।" সরাসরি-child চেকের ফাঁদে পড়বে না। বিকল্পে inorder strictly increasing কিনা দেখো। যেকোনো subtree-ব্যাপী constraint-এ এই bounds-passing চাল মনে করবে।

25. JavaScript solution (with test cases)¶

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 ফাঁদ।

26. TypeScript solution (with test cases)¶

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 সঠিক থাকে।

27. কোথায় কাজে লাগে (real-world use)¶

Database index integrity: একটা B-tree/BST-ভিত্তিক index সত্যিই sorted invariant মানছে কিনা যাচাই করা — corruption detection বা migration-এর পরে।
Configuration / threshold validation: কোনো নিয়মে যদি প্রতিটা সীমা তার parent-range-এর ভেতরে থাকতে হয় (nested range), এই bounds-passing চেক ঠিক সেই কাজ করে।
Form / input range checking: nested রেঞ্জ-নির্ভর input (যেমন min ≤ value ≤ max, আর max আবার একটা বড় range-এ) যাচাই করতে একই ধারণা।
Compiler / type checker: scope-এর ভেতরে variable-এর valid range বা constraint propagate করতে similar "constraint নিচে বহন করো" technique।
Game / simulation rules: একটা hierarchical rule-set যেখানে child-এর allowed value parent দিয়ে সংকুচিত হয় — সেটা সঙ্গতিপূর্ণ কিনা যাচাই।

মূল সুর: যখনই কোনো property "শুধু সরাসরি প্রতিবেশী নয়, পুরো subtree/scope-কে বাঁধে" — constraint-টা recursion-এর argument হিসেবে নিচে নিয়ে যাও।

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