4

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?

4
  • 2
    It's a typo. Your nodes have a value property your testing for val : (root.val <= min Commented Aug 7, 2018 at 2:25
  • Also, I'm curious what Object.extend is contributing. It seems like node.create could simply be create: function (value, left=null, right=null) { return Object.assign(Object.create(node), { value, left, right }) } Commented Aug 7, 2018 at 2:36
  • The author of the blog post used it as a helper function for assigning values to properties of copied objects. However, I agree using Object.assign is a much simpler design. Commented Aug 7, 2018 at 4:41
  • @MarkMeyer what would be better performance wise? The extend function or the Object.assign method you suggested. Commented Aug 7, 2018 at 5:06

1 Answer 1

2

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.

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

1 Comment

Thanks! Have to keep my eyes open for those little mistakes.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.