Good evening! Here's our prompt for today.

Given a binary search tree like the one below, can you write a function that will return true if it is valid?

1    5 
2   / \ 
3  3   9 
4 / \
51   4

Recall that a BST is valid only given the following conditions:

• The left child subtree of a node contains only nodes with values less than the parent node's.
• The right child subtree of a node contains only nodes with values greater than the parent node's.
• Both the left and right subtrees must also be BSTs.

You can assume that all nodes, including the root, fall under this node definition:

1class Node {
2	constructor(val) {
3		this.value = val;
4		this.left = null;
5		this.right = null;
6	}
7}

The method may be called like the following:

1root = new Node(5);
2root.left = new Node(3);
3root.right = new Node(9);
4
5console.log(isValidBST(root));

Constraints

• Length of the given tree <= 100000
• The nodes in the tree will always contain integer values between -1000000000 and 1000000000
• Expected time complexity : O(n)
• Expected space complexity : O(logn) or O(d) where d is the depth of the tree

Try to solve this here or in Interactive Mode.

How do I practice this challenge?

xxxxxxxxxx

  console.log('PASSED: ' + '`isValidBST(tree1)` should return `false`');

var assert = require('assert');

​

function isValidBST(self, root) {

  // Fill in this method

  return self;

}

​

function inOrder(root, output) {}

​

function Node(val) {

  this.val = val;

  this.left = null;

  this.right = null;

}

​

// Regular binary trees

var tree1 = new Node(4);

tree1.left = new Node(1);

tree1.right = new Node(3);

​

var tree2 = new Node(5);

tree2.left = new Node(10);

tree2.left.left = new Node(17);

tree2.left.right = new Node(3);

tree2.right = new Node(8);

​

// Binary search trees

var tree3 = new Node(6);

tree3.left = new Node(3);

We'll now take you through what you need to know.

How do I use this guide?