Check whether tree is binary search tree query

So, for the following challenge:

I wrote the following code:

var displayTree = (tree) => console.log(JSON.stringify(tree, null, 2));
function Node(value) {
  this.value = value;
  this.left = null;
  this.right = null;
}

function isBinarySearchTree(tree) {
  // Only change code below this line
  
  function isBinarySubTree(node){
    
    //no node
    if (node == null) return true;
  
    //left node check  
    if (node.left && node.left.value > node.value) return false;

    //right node check            
    if (node.right && node.right.value < node.value) return false;

    //recursion for further children            
    if (node.left && !isBinarySearchTree(node.left) || node.right && !isBinarySearchTree(node.right))
          return false;      
      
    return true;
  }

  //passing root node
  return isBinarySubTree(tree.root)
  
  // Only change code above this line
}

So I tested this by creating an add node method and passing a non binary tree and a binary tree, alongwith the no root node and single root node cases. The output comes out correct in console. But I am unable to pass test.

What am I missing

What happens if the root value is equal to a child value?

You need some ()s in here to get correct precedence

ah, right! Added the <=
Also grouped the AND conditions - but still not passing the tests.

var displayTree = (tree) => console.log(JSON.stringify(tree, null, 2));
function Node(value) {
  this.value = value;
  this.left = null;
  this.right = null;
}

function BinarySearchTree() {
  this.root = null;
}

function isBinarySearchTree(tree) {
  // Only change code below this line
  
  function isBinarySubTree(node){
    
    //no node
    if (node == null) return true;
  
    //left node check  
    if (node.left && node.left.value > node.value) return false;

    //right node check            
    if (node.right && node.right.value <= node.value) return false;

    //recursion for further children            
    if ((node.left && !isBinarySubTree(node.left)) || (node.right && !isBinarySubTree(node.right)))
          return false;      
      
    return true;
  }

  //passing root node
  return isBinarySubTree(tree.root)
  
  // Only change code above this line
}

Nodes have at most 2 child nodes (placed to the right and/or left) based on if the child node’s value is greater than or equal to (right) or less than (left) the parent node.

I think that the equal goes on the left when you negate these expressions.

ah yes!! just checked that (before reading the reply, haha) and was about to post my correction, but you replied! Thanks for the help

1 Like

Though, I was wondering about a general query in regards to binary tree - As it goes, all left child nodes are small that parent and right nodes are greater than parent. But if it’s equal then It can only go to right or left - So, is there a standard for it - or is it just defined differently according to whoever is using it?

I’m not aware of a specific convention. Since a user wouldn’t directly touch the internals of your tree, I probably doesn’t make a huge difference which one you pick.

oh, ok - since this is just implementation for purpose of internal working understanding. But, otherwise it would be pre-defined

1 Like