How to write this JavaScript code for finding if a tree is a Binary Search Tree in fewer lines?

Question

In a quiz for my Javascript class, we were told to make a simple tree and write a function that returns true or false whether it is a BST or not.

I got a decent grade, but i got 10 points off because the instructor said "It can be done in 6 less lines".

This is what I had:

function node(value, left, right){
    this.Value = value;
    this.Left = left;
    this.Right = right;
}

//this IS a BST, returns true
var head = new node(8, new node(9, null, null), new node(10, new node(9, null, null), new node(14, new node(13, null, null), null)));


function isBST(currNode){
    if(currNode.Left === null && currNode.Right === null){
        return true;
    }
    else if(currNode.Left.Value > currNode.Value || currNode.Right.Value < currNode.Value){
        return false;
    }
    else{
        if(currNode.Left === null){
            return isBST(currNode.Right);
        }
        else if(currNode.Right === null){
            return isBST(currNode.Left);
        }
        else{
            return (isBST(currNode.Left) && isBST(currNode.Right));
        }
    }
}


console.log(isBST(head));

Anything I'm overlooking here? Maybe it shouldn't have been recursive?

Minify it and give it to them as one line... joking! The second return statement in your else condition is unreachable though. — Kyle Richardson
– Kyle Richardson, Commented Jul 27, 2017 at 14:38
Yes it is. You could also remove curly braces from arounf if statements that are one line... like James said though... readable code > less lines. Teacher seems bad to me... You should of lost 10 points for the extraneous return, not line count. — Kyle Richardson
– Kyle Richardson, Commented Jul 27, 2017 at 14:45
I think it's fair to assume the teacher isn't marking him down on using curly braces. I expect that you can greatly reduce the conditions with some careful reshuffling — musefan
– musefan, Commented Jul 27, 2017 at 14:46
@Team.Coco: Can you provide the definition of a binary search tree? Preferably from the assignment spec? — musefan
– musefan, Commented Jul 27, 2017 at 14:47

Matt Timmermans · Accepted Answer · 2017-07-27 15:42:01Z

4

The problem with your current function is that it does not work. It returns true for:

It seems that all the other answers at this time have the same problem. Here's one that works and is a lot shorter

function isBST(curNode, minval, maxval){
    if (curNode == null) {
        return true;
    }
    return (
        (minval == null || minval <= curNode.Value) &&
        (maxval == null || maxval >= curNode.Value) &&
        isBST(curNode.Left, minval, curNode.Value) &&
        isBST(curNode.Right, curNode.Value, maxval)
    );
}

edited Jul 27, 2017 at 15:42

answered Jul 27, 2017 at 15:33

Matt Timmermans

60.9k3 gold badges57 silver badges106 bronze badges

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

7 Comments

Kyle Richardson Over a year ago

up voted, but his teacher doesn't actually look at the code to see if it works.

darKnight Over a year ago

Why is above [4,3,5,2,100] not a BST? All left nodes are less than parent and all right nodes are greater than it's parent..

Matt Timmermans Over a year ago

@maverick because that is not the whole criteria. All the nodes left of 4 have to be less than or equal to 4, but 100 is not less than 4.

darKnight Over a year ago

@MattTimmermans I have never seen this criteria anywhere. See geeksforgeeks.org/binary-search-tree-data-structure What you are referring to is max-heap data structure, which is a special case of Binary Tree. See tutorialspoint.com/data_structures_algorithms/….

Matt Timmermans Over a year ago

@maverick let's say you are searching for 100 in a BST. You start at the root. The root has value 4. Will you go left or right? Oh, look, you didn't find it because my BST is invalid! Also, you should read the GFG article you linked more closely.

|

Kyle Richardson · Accepted Answer · 2017-07-27 16:06:37Z

If all your teacher is worried about is line count... I would consider them to be a bad teacher...

That being said... I'm not saying your code is correct, but here is your code minus the extraneous return statement, with more than 6 less lines.

function node(value, left, right){
    this.Value = value;
    this.Left = left;
    this.Right = right;
}

//this IS a BST, returns true
var head = new node(8, new node(9, null, null), new node(10, new node(9, null, null), new node(14, new node(13, null, null), null)));

function isBST(currNode){
    if(currNode.Left === null && currNode.Right === null) return true;
    if(currNode.Left.Value > currNode.Value || currNode.Right.Value < currNode.Value) return false;
    if(currNode.Left === null) return isBST(currNode.Right);
    if(currNode.Right === null) return isBST(currNode.Left);
    return (isBST(currNode.Left) && isBST(currNode.Right));
}

console.log(isBST(head));

As an aside: verbose readable code trumps less lines and hard to read 99.99% of the time. 0.01% is when you're in a bad teacher's class who cares more about line count than actually looking at your assignment.

Aside #2: A line more than ~80 characters in length should normally be split into multiple lines for readability. No one likes to read one long line of code.

EDIT: For a real BST modeled after the example @ stanford.edu

var head = new node(5,
    new node(3,
        new node(1, null, null),
        new node(4, null, null)
    ),
    new node(9,
        new node(6, null, null),
        null
    )
);

Collectives™ on Stack Overflow

How to write this JavaScript code for finding if a tree is a Binary Search Tree in fewer lines?

2 Answers 2

7 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

7 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related