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
– bhspencer, Commented Dec 2, 2015 at 14:35
Because you pass in node.val isValidBST(node.right, node.val, max) so node.val must not be null. — bhspencer
– bhspencer, Commented Dec 2, 2015 at 14:37
Everything you ever wanted to know about this is here: stackoverflow.com/questions/499995/… — m69 ''snarky and unwelcoming''
– m69 ''snarky and unwelcoming'', Commented Dec 3, 2015 at 1: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
– devdropper87, Commented Dec 3, 2015 at 15:01

maxshuty · Accepted Answer · 2021-10-23 20:50:38Z

3

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));

edited Oct 23, 2021 at 20:50

maxshuty

10.9k13 gold badges71 silver badges87 bronze badges

answered Oct 7, 2018 at 17:52

ASHISH R

4,1891 gold badge24 silver badges16 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

bhspencer · Accepted Answer · 2015-12-03 16:32:28Z

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 3, 2015 at 16:32

bhspencer

13.7k5 gold badges38 silver badges44 bronze badges

Comments

user12200634 · Accepted Answer · 2020-03-18 14:56:18Z

1

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)
  );
};

answered Mar 18, 2020 at 14:56

user12200634

Comments

Yuniel · Accepted Answer · 2021-04-11 01:21:46Z

0

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;
};

edited Apr 11, 2021 at 1:21

answered Apr 4, 2021 at 18:31

Yuniel

13 bronze badges

Collectives™ on Stack Overflow

Checking if a Binary Search Tree is Valid javascript

4 Answers 4

Comments

Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related