Checking if a Binary Search Tree is Valid javascript

Question

I came across this problem online and I found the following function to check if a BST is valid. However, what I don't fully understand is how max/min change from null to values that you can compare against. so in the following function:

//Give the recursive function starting values:

 function checkBST(node) {
  // console.log(node.right);
  return isValidBST(node, null, null);
}


 function isValidBST(node, min, max) {
  console.log(min, max);


  if (node === null) {

    return true;
  }

  if ((max !== null && node.val > max) || (min !== null && node.val < min)) {

    return false;
  }

  if (!isValidBST(node.left, min, node.val) || !isValidBST(node.right, node.val, max)) {

    return false;
  }
  return true;
}



var bst = new BinarySearchTree(8);
bst.insert(3);
bst.insert(1);
bst.insert(6);
bst.insert(10);
bst.insert(4);

when you come back up from the lowest depth on the left it compares the value at the lowest depth with the depth right above it (ie when 1 3 is output). somehow min goes from null to 1 and I'm not seeing how, I was thinking you would need some sort of a base case for the minimum to change from null to something else... I get this in the console when I console.log min/max on each run.

null null
null 8
null 3
null 1
1 3
3 8
3 6
3 4
4 6
6 8
8 null
8 10
10 null

you are explicitly calling isValidBST with non null values with this expression `if (!isValidBST(node.left, min, node.val) || !isValidBST(node.right, node.val, max)) { ` — bhspencer, Dec 02 '15 at 14:35
Because you pass in node.val `isValidBST(node.right, node.val, max)` so node.val must not be null. — bhspencer, Dec 02 '15 at 14:37
Everything you ever wanted to know about this is here: http://stackoverflow.com/questions/499995/how-do-you-validate-a-binary-search-tree — m69's been on strike for years, Dec 03 '15 at 01:42
@bhspencer oh I think I get it now. those two separate function calls know about each other's variables (min, max), I think that's what was tripping me up. feel free to post as answer and I will accept! — devdropper87, Dec 03 '15 at 15:01

score 3 · Answer 1 · edited Oct 23 '21 at 20:50

Given a node, validate the binary search tree, ensuring that every node's left hand child is less than the parent node's value, and that every node's right hand child is greater than the parent

class Node {
constructor(data) {
this.data = data;
this.left = null;
this.right = null;
 }
}

class Tree {
 constructor() {
 this.root = null;
}

isValidBST(node, min = null, max = null) {
if (!node) return true;
if (max !== null && node.data >= max) {
  return false;
}
if (min !== null && node.data <= min) {
  return false;
}
const leftSide = this.isValidBST(node.left, min, node.data);
const rightSide = this.isValidBST(node.right, node.val, max);

return leftSide && rightSide;
}
}

const t = new Node(10);
t.left = new Node(0);
t.left.left = new Node(7);
t.left.right = new Node(4);
t.right = new Node(12);
const t1 = new Tree();
t1.root = t;
console.log(t1.isValidBST(t));

score 2 · Accepted Answer · answered Dec 03 '15 at 16:32

2

The variable min becomes non null because you explicitly call

isValidBST(node.right, node.val, max)

where you are passing node.val as the param min. It must be that at the point you make this call node.val is not null;

answered Dec 03 '15 at 16:32

bhspencer

13,086
5
35
44

score 1 · Answer 3 · answered Mar 18 '20 at 14:56

Another solution could be:

const isValidBST = (
  root,
  min = Number.MIN_SAFE_INTEGER,
  max = Number.MAX_SAFE_INTEGER
) => {
  if (root == null) return true;
  if (root.val >= max || root.val <= min) return false;
  return (
    isValidBST(root.left, min, root.val) &&
    isValidBST(root.right, root.val, max)
  );
};

Yuniel · Answer 4 · 2021-04-11T01:21:46.813

Checking if a Binary Search Tree is Valid:

class BTNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

/**
 *
 * @param {BTNode} tree
 * @returns {Boolean}
 */
const isBinarySearchTree = (tree) => {
  if (tree) {
    if (
      tree.left &&
      (tree.left.value > tree.value || !isBinarySearchTree(tree.left))
    ) {
      return false;
    }
    if (
      tree.right &&
      (tree.right.value <= tree.value || !isBinarySearchTree(tree.right))
    ) {
      return false;
    }
  }
  return true;
};

Checking if a Binary Search Tree is Valid javascript

4 Answers4