Skip to content

Instantly share code, notes, and snippets.

@pablolmiranda
Created August 26, 2016 17:37
Show Gist options
  • Save pablolmiranda/01d58561e9894615d8a2fd007ac36a13 to your computer and use it in GitHub Desktop.
Save pablolmiranda/01d58561e9894615d8a2fd007ac36a13 to your computer and use it in GitHub Desktop.
Check if a BST is valid
function isBST(root) {
return validate(root, Number.MIN_SAFE_INTEGER, Number.MAX_SAFE_INTEGER);
}
function validate(node, min, max) {
if (node === null) {
return true;
}
if (node && node.value < min) {
return false;
}
if (node && node.value > max) {
return false;
}
return validate(node.left, min, node.value)
&& validate(node.right, node.value, max);
}
function Node(value, leftNode, rightNode) {
this.value = value;
this.left = leftNode;
this.right = rightNode;
}
var n1 = new Node(5, null, null),
n2 = new Node(1, null, n1),
subtree = new Node(2, n2, null),
invalidTree = new Node(10, subtree, null),
ln = new Node(1, null, null),
rn = new Node(3, null, null),
validateTree = new Node(2, ln, rn);
console.log('is a BST: ', isBST(invalidTree), ', this is not a BST');
console.log('is a BST: ', isBST(validateTree), ', this is a BST');
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment