Good morning! 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?

SNIPPET
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:
JAVASCRIPT
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:
JAVASCRIPT
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
and1000000000
- Expected time complexity :
O(n)
- Expected space complexity :
O(logn)
orO(d)
whered
is the depth of the tree
Try to solve this here or in Interactive Mode.
How do I practice this challenge?
xxxxxxxxxx
70
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);
OUTPUT
:001 > Cmd/Ctrl-Enter to run, Cmd/Ctrl-/ to comment
Here's our guided, illustrated walk-through.
How do I use this guide?