Validate Binary Search Tree in Javascript

In this post I’ll be going over a solution to Leetcode problem 98. Validate Binary Search Tree.

The problem statement reads:

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

A valid BST is defined 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.

We know that there are rules that must be true for each node in the tree in relationship to each other. In other words, we want to scan each node in the tree, and confirm it meets the rules for a BST. Given that we are working with a tree and we want to evaluate relationships of each node, this is a good problem for recursion.

So in thinking about our rules for a BST, how might we reflect these in a recursive function? We know that for each subtree/ every subtree in the BST, the left subtree contains only nodes that have values greater than the parent node and the right subtree contains only nodes that have value less than the parent. We can think about checking the validity of each subtree as comparing root.left and root.right to a min and max value respectively.

So, if we think about recursing down the left subtree, we know that we need to check if each node is less than the node above it. One way to do this is to assign and reassign a max value as we recurse down the tree, in order to check that each child node is not greater than or equal to its parent. We do the inverse of that check as we go down the right subtree of each node.

With this, we can think about a helper function that takes 3 arguments: the node being processed, the max value against which to compare the left children, and the min value against which to compare the right children. In our helper function we can return a call for the left subtree in which the max value is dynamically reassigned each time and vice versa for the right.

With each call, if we are looking at the left child, we check if the node is greater than or equal to the max (i.e. the value of its parent). If it is, we return false. If we are looking at a right child, we check if the node is less than or equal to the min (the value of its parent). If it is, we return false.

At the bottom of the helper function we return two calls to the function: one for the left subtree and one for the right.

So for any given call, how do we discern if we are looking at the left subtree and need to compare against a max, or the right subtree and need to compare against a min? The answer comes in the first call to our function and how we structure our conditional statement.

We do not need to check whether the root of the tree is greater than or less than anything. We just need it to be there. With the first call of the helper function then, we call it with the root node, and the min and max values both assigned to null.

With each call, we only reassign the value against which we need to compare children, and we keep the other value at null. So if we are calling for a left child we call helper(root.left, min, root.val). As a result, the max value is reassigned each time, and the min value stays at null. This way, in order to check the rules in our tree, we group together checking whether the min (or max) is null, and then we compare root.val to the min or max appropriately. We return false if the current node does not have the correct relationship with the value of the parent.

Our base case is to check if there is no root node (i.e. we have reached the end of our tree/ call stack), return true. This means we have compared each node in our tree against our rules and have not returned false.

All of this may seem confusing, but is much easier to understand coded out. Here is the code below:

Hope this helps!