AlgoDaily - Validate a BST

Validate a BST (Medium)

Good evening! Here's our prompt for today.

You may see this problem at Cisco, Flipkart, Linkedin, Palantir, Groupon, Coursera, Robinhood, Auth0, Appdirect, Zynga, Icims, and Elastic.

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

SNIPPET

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 and 1000000000
Expected time complexity : O(n)
Expected space complexity : O(logn) or O(d) where d is the depth of the tree

xxxxxxxxxx
​
 
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

OUTPUT

Results will appear here.