LeetCode JS Algo Problem: Validate Binary Search Tree

Photo by Markus Spiske on Unsplash

Solving this medium level leet code problem was frustrating to say the least. After learning how to solve such problem, I can explain how to approach such problem.

The problem: Given the root of a binary tree, determine if it is a valid binary search tree (BST).

A valid binary search tree is as follows:

• The left subtree of a node contains only nodes with keys less than the node’s key.
• The right subtree of a node contains only nodes with keys greater than the node’s key.
• Both the left and right subtrees must also be binary search trees.

Example 1:

Input: root = [2,1,3]
Output: true

The result of this BST is true because the left node’s key is less then the root value and the right node’s key is greater then the root’s value.

Example 2:

Input: root = [5,1,4,null,null,3,6]
Output: false
Explanation: The root node's value is 5 but its right child's value is 4.

The result of this BST is false because only the left node meets the requirements for being a BST and since the right node is lower then the root value, the overall output will return false.

Starting off:

function isValidBST(root) {

};

We have the function isValidBST with the sole parameter of root. Since there are two things we have to look at in order to determine the validity of the BST, we can add two more parameters to the isValidBST function and call them max and min. Understanding that we would need to examine more then one value to determine the BST’s validity, we will use if statements. With our first if statement we want to define our base case and that is if the amount is not the root value in general, then we will determine it’s true. This is just simply stating if the amount that branches off from the root value and it can be either lesser or greater then that amount, then we know it’s true.

function isValidBST(root, min, max) {

if (!root) {
return true;
}

};

Then after stating our first if statement, we move on to our second and third. For both of these statements, we can say if the min and max value exists and the root value is either less then or greater then the min and max values respectfully, we will return false.

if (min !== undefined && root.val < min) {
return false;
}

if (max !== undefined && root.val > max) {
return false;
}

Since this approach is recursion, we want to call the function isValidBST and input our new params for the following sub binary search tree.

return isValidBST(root.left, min, root.val) && isValidBST(root.right, root.val, max);