Skip to content

019 — Validate Binary Search Tree

Source

  • Original source: Classic cross-topic capstone interview problem (BST property checking)
  • Platform: LeetCode — https://leetcode.com/problems/validate-binary-search-tree/
  • 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।

1. Problem in simple words

তোমাকে একটা binary tree-র root দেওয়া আছে। তোমার কাজ: বলো এটা একটা বৈধ Binary Search Tree (BST) কিনা। BST-র নিয়ম: প্রতিটা node-এর জন্য — তার পুরো left subtree-র সব মান node-এর চেয়ে ছোট, আর তার পুরো right subtree-র সব মান node-এর চেয়ে বড় হতে হবে। শুধু True/False চাই।

       5
      / \
     1   8     ->  left(1) < 5 < right(8), দুই subtree-ও ঠিক  ->  True

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 সংকুচিত করি —

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-ই যথেষ্ট।

6. Real-life analogy

ভাবো একটা সাংগঠনিক চার্ট, যেখানে প্রতিটা পদের একটা "অনুমোদিত বেতন-পরিসর" আছে যা উপরের বসদের সিদ্ধান্ত থেকে নেমে আসে। তুমি ওপর থেকে নিচে নামছ — বাঁ শাখায় গেলে সর্বোচ্চ সীমা কমে (current বসের চেয়ে কম হতে হবে), ডান শাখায় গেলে সর্বনিম্ন সীমা বাড়ে। প্রতিটা পদের বেতন তার গড়িয়ে-আসা পরিসরের ভেতরে থাকতে হবে — একটাও বাইরে গেলে পুরো চার্ট অবৈধ।

7. Visual explanation

একটা অবৈধ গাছ দেখি — চোখে ঠিক মনে হলেও range ধরে ফেলে:

        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 সেটা ধরে।

8. Example input and output

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 <

9. Brute force thinking

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

একটা সঠিক brute force: প্রতিটা node-এর জন্য তার পুরো left subtree-র max আর right subtree-র min আলাদা করে বের করে তুলনা করা।

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 আপনিই ধরা পড়ে, এক পাসেই।

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।

15. Python solution

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 দিয়ে শুরু।

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

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-পদ্ধতিই সরল)।

21. Which basic problem this inherits from

ভিত্তি: binary tree-র উপর recursive traversal আর BST-property বোঝা (07 trees-এর ../../07-trees/) + প্রতিটা recursive call-এ extra state (low, high) বহন করা (06 recursion-এর ../../06-recursion-and-backtracking/)। এই দুটো cold অবস্থায় জানা থাকলে range-passing validation নিজে থেকেই বেরিয়ে আসে।

22. Similar harder problems

23. Pattern learned

Range-passing recursion: প্রতিটা node-কে একটা বৈধ (low, high) ব্যবধান দিয়ে যাচাই করা, আর নিচে নামার সময় ব্যবধান সংকুচিত করা (left-এ high↓, right-এ low↑)। ancestor-দের সব constraint একটা range-এ গুটিয়ে এক পাসে O(n) যাচাই — trees + recursion combo-র canonical রূপ।

24. Final summary

ভবিষ্যতের আমাকে: "tree-টা বৈধ BST কিনা" দেখলেই range-passing recursion মনে করবে — root শুরু করো (-inf, +inf) দিয়ে, প্রতি node-এ low < val < high strict চেক, left-এ (low, val), right-এ (val, high)। শুধু সরাসরি child দেখো না — deep violation মিস হবে। strict < রাখো (duplicate trap)। trees-traversal আর state-passing recursion-এর সবচেয়ে পরিষ্কার মেলবন্ধন।

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