5.4 Validation & Properties

চিনবেন কীভাবে

"validate BST", "balanced", "diameter", "symmetric/invert" — subtree থেকে property (height, range) উপরে ওঠানো

Demo · approach · কোড — আগে নিজে চেষ্টা, আটকালে খুলুন

Demo: Validate Binary Search Tree — LC 98 (Medium — Amazon/Microsoft High)

Statement (Demo): binary tree-এর root দেওয়া — এটা valid BST কিনা বলুন। BST মানে: প্রতিটা নোডের left subtree-র সব মান নোডের চেয়ে strictly ছোট, right subtree-র সব মান strictly বড়। উদাহরণ: root=[5,1,4,null,null,3,6] → false (4-এর right-এ 3, কিন্তু 3 < 5) | ⚡ n ≤ 10⁴

Approach: শুধু parent-child তুলনা করলেই ভুল — পুরো subtree-র valid range (min, max) নামিয়ে দিতে হবে। বামে গেলে max হয় নোডের মান, ডানে গেলে min।

function isValidBST(root, min = -Infinity, max = Infinity) {
  if (!root) return true;
  if (root.val <= min || root.val >= max) return false;
  return (
    isValidBST(root.left, min, root.val) &&
    isValidBST(root.right, root.val, max)
  );
}

Complexity: Time O(n), Space O(h)

প্রবলেম

Balanced Binary TreeLC 110
(height ফেরত দিন, unbalanced হলে -1 sentinel)
Statement: binary tree-এর root দেওয়া — height-balanced কিনা বলুন। (Height-balanced মানে প্রতিটা নোডের left ও right subtree-র height-এর পার্থক্য সর্বোচ্চ 1।)
উদাহরণ: root=[3,9,20,null,null,15,7] → true | ⚡ n ≤ 5000
নোট · ফাঁকা
আমার সমাধান — মূল আইডিয়া ২–৩ লাইনে, ইংরেজিতেযে সমস্যা হয়েছিল — কোন trap বা edge case-এ আটকালেন
Diameter of Binary Treeplan · দিন ০৩৭ LC 543
(Max Path Sum-এর ছোট ভাই — একই কাঠামো)
Statement: binary tree-এর root দেওয়া — tree-এর diameter (যেকোনো দুটো node-এর মধ্যে দীর্ঘতম path-এর length, edges-এ) বের করুন।
উদাহরণ: root=[1,2,3,4,5] → 3 (4→2→1→3 বা 5→2→1→3) | ⚡ n ≤ 10⁴
নোট · ফাঁকা
আমার সমাধান — মূল আইডিয়া ২–৩ লাইনে, ইংরেজিতেযে সমস্যা হয়েছিল — কোন trap বা edge case-এ আটকালেন
Invert Binary Treeplan · দিন ০২৬ LC 226
Statement: binary tree-এর root দেওয়া — tree-টি invert করুন (প্রতিটা নোডের left ও right child swap করুন) এবং root return করুন।
উদাহরণ: root=[4,2,7,1,3,6,9] → [4,7,2,9,6,3,1] | ⚡ n ≤ 100
নোট · ফাঁকা
আমার সমাধান — মূল আইডিয়া ২–৩ লাইনে, ইংরেজিতেযে সমস্যা হয়েছিল — কোন trap বা edge case-এ আটকালেন
Symmetric TreeLC 101
(দুই নোড নিয়ে mirror তুলনা)
Statement: binary tree-এর root দেওয়া — tree-টি নিজের mirror কিনা (symmetric around its center) true/false বলুন।
উদাহরণ: root=[1,2,2,3,4,4,3] → true | ⚡ n ≤ 1000
নোট · ফাঁকা
আমার সমাধান — মূল আইডিয়া ২–৩ লাইনে, ইংরেজিতেযে সমস্যা হয়েছিল — কোন trap বা edge case-এ আটকালেন