CODEWITHSUNDEEP
javascriptbinary-search-treeprototypal-inheritance
Arban Nichols
Arban Nichols

Reputation: 51

Why does this BST validation function fail with this javascript tree implementation?

I'm trying to understand how to create objects in js using prototypal inheritance i.e using Object.create() instead of the new keyword. I created a node class for the purposes of making a tree data structure using the implementation below:

Object.prototype.extend = function(extension) {
    var hasOwnProperty = Object.hasOwnProperty;
    var object = Object.create(this);

    for(var property in extension) {
      if (hasOwnProperty.call(extension, property) ||
              typeof object[property] === "undefined")
                    object[property] = extension[property];
    }

    return object

}

const node =  {
    create: function (value, left=null, right=null) {
      return this.extend({
        value: value,
        left: left,
        right: right,
      })
    },
    insertLeft: function(value){
        this.left = this.create(value);
        return this.left;
    },
    insertRight: function(value) {
        this.right = this.create(value);
        return this.right;
    }
}

The extend function I received from a blog post explaining prototypal inheritance.

I then made a function to validate a BST implemented as such:

validateBST = function (root) {
    if (root === null) return true
    return (function validate(root, min=-Infinity, max=Infinity) {
      if (root === null) return true
      if (root.val <= min || root.val >= max) return false
      return validate(root.left, min, root.val) && validate(root.right, root.val, max)
    })(root)
}

I initialize my tree using the create method in my node object.

let tree = node.create(5, node.create(1), node.create(4, node.create(3), node.create(6)));

Output of tree variable;

{ value: 5,
  left: { value: 1, left: null, right: null },
  right:
   { value: 4,
     left: { value: 3, left: null, right: null },
     right: { value: 6, left: null, right: null } } }

So this is an invalid BST but my function returns true, why?

Upvotes: 4

Views: 151

Answers (1)

Karan Bhagat
Karan Bhagat

Reputation: 329

It is because the validateBST function is assuming that the root parameter will have a property 'val', but you are passing a node object which has property 'value'. Now why it returns true, because root.val will be undefined and will never enter the only 'if' statement that returns false. And, the execution will go until it hit tree leaves where root is null and hence returns true. Only change you need is to replace 'root.val' with 'root.value' in the validateBST() function.

Upvotes: 2

Related Questions