Checking if a Binary Search Tree is Valid javascript

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

Answer

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;

Advertisement

Answer