Given the root of a binary tree, determine if it is a valid binary search tree (BST).
A valid BST is defined as follows:
The left subtree of a node contains only nodes with keys less than the node's key.
The right subtree of a node contains only nodes with keys greater than the node's key.
Both the left and right subtrees must also be binary search trees.
Example 1:
Input: root = [2,1,3]
Output: true
Approach 1 : keeping two values max & min Range
var isValidBST = function (root) {
return validate(root, -Infinity, Infinity);
};
var validate = function (node, lower, upper) {
if (node == null) {
// empty node or empty tree
return true;
}
if (lower < node.val && node.val < upper) {
// check if all tree nodes follow BST rule
return (
validate(node.left, lower, node.val) &&
validate(node.right, node.val, upper)
);
} else {
// early reject when we find violation
return false;
}
};
Approach 2 : Performing in order Traversal & thn checking array with sorted array.
var isValidBST = function (root) {
function inOrder(node) {
if (!node) return [];
return [...inOrder(node.left), node.val, ...inOrder(node.right)];
}
const sortedArr = inOrder(root);
for (let i = 0; i < sortedArr.length; i++) {
if (sortedArr[i + 1] <= sortedArr[i]) return false;
}
return true;
};
Approach 3 : Performing InOrder Traversal & keeping one Min Pointer to perform comparison
var isValidBST = function (root) {
let previous = -Infinity;
function checkInOrder(root) {
if (root === null) {
return null;
}
if (checkInOrder(root.left) === false) {
return false;
}
if (root.val <= previous) {
return false;
}
previous = root.val;
return checkInOrder(root.right);
}
return checkInOrder(root);
};
Top comments (0)