5.4 Validation & Properties
Demo · approach · কোড — আগে নিজে চেষ্টা, আটকালে খুলুন
Demo: Validate Binary Search Tree — LC 98 (Medium — Amazon/Microsoft High)
Statement (Demo): Given the root of a binary tree, decide whether it is a valid BST: every value in a node's left subtree is strictly smaller, every value in its right subtree strictly larger.
Example: root=[5,1,4,null,null,3,6] → false (3 sits right of 4, but 3 < 5) | ⚡ n ≤ 10⁴
Approach: Comparing only parent and child is wrong — pass the whole subtree's valid range (min, max) down. Going left, the max becomes the node's value; going right, the min does.
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(return height, -1 as the "unbalanced" sentinel)
Statement: Given the
rootof a binary tree, decide whether it is height-balanced — at every node, the heights of the two subtrees differ by at most 1.
Example:root=[3,9,20,null,null,15,7]→true| ⚡n ≤ 5000নোট · ফাঁকা
- Diameter of Binary Treeplan · দিন ০১৫LC 543(little brother of Max Path Sum — same shape)
Statement: Given the
rootof a binary tree, return its diameter — the length, in edges, of the longest path between any two nodes.
Example:root=[1,2,3,4,5]→3(4→2→1→3 or 5→2→1→3) | ⚡n ≤ 10⁴নোট · ফাঁকা
- Invert Binary Treeplan · দিন ০০৩LC 226
Statement: Given the
rootof a binary tree, invert it (swap every node's left and right child) and return the root.
Example:root=[4,2,7,1,3,6,9]→[4,7,2,9,6,3,1]| ⚡n ≤ 100নোট · ফাঁকা
- Symmetric TreeLC 101(mirror comparison of two nodes)
Statement: Given the
rootof a binary tree, return whether it is a mirror of itself (symmetric around its center).
Example:root=[1,2,2,3,4,4,3]→true| ⚡n ≤ 1000নোট · ফাঁকা