AlgoDaily - Validate a BST - Complexity Of Final Solution

If this is in sorted order, we know that this is valid. We can check this iterating through the returned list, checking that each iterated element's value is greater than the previous iteration's. If we get to the end, we can return True. If the opposite is ever true, we'll immediately return False.

Complexity of Final Solution

Let n be the size of the tree. We traverse through all n tree nodes using recursion for O(n) time complexity, and we have O(logn) space complexity due to recursion or O(d) where d is the depth of the tree.

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

OUTPUT

Results will appear here.