Leetcode - Validate Binary Search Tree (with JavaScript)

Today I am going to show how to solve the Validate Binary Search Tree.

Here is the problem:

Before explaining the solution to this problem, I am going to shortly go over what a Binary Search Tree (BST) is.

Generally a tree is a data structure composed of nodes. Each tree has a root node which is the highest node and has zero or more child nodes. As stated in the problem, a Binary Search Tree is a type of tree in which each node has up to two children and adheres to the following properties:

• 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.

Based on all of this, we can say that every node in BST has a minimum value and a maximum value.

Therefore, I am going to traverse the entire given tree by starting from the root node. Then, I move down from the root to validate all the subtrees by checking if all of the subtrees’ nodes are wrapped between their minimum value and maximum value. I will do this until I reach null values i.e. leaf nodes that don't have any child nodes.

For this, I created a helper method (validateBst) which takes in additional arguments, a minValue and a maxValue, and I pass down values as we traverse the tree. When I call the helper method on the left subtree of a node, I change the maximum value to be the value of our current node. When I call the function on our left subtree, I change the maximum value to be the current value of our node.

var isValidBST = function(root) {
    return validateBst(root, -Infinity, Infinity)
};

function validateBst(root, minValue, maxValue) {
    if(root == null) return true;
     if(root.val >= maxValue || root.val <= minValue) return false;
    return validateBst(root.right, root.val, maxValue) &&
            validateBst(root.left, minValue, root.val)
}