Validate Binary Search Tree: Explanation + Interactive Demo

The Problem

The problem statement is as follows:

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.

And they have also given a few examples.

In Order To Understand The Problem…

I think there are 2 concepts you will need in order to understand the problem and what is being asked:

1. What is a Binary Search Tree?
2. How exactly is the Array being used to represent the Binary Search Tree?

So, let me provide you with the best resources I could find in order to help with these 2 sub-topics.

Prior Knowledge Sub-Topic 1: What is a Binary Search Tree? What is it used for? What kind of problems does it help us solve? Why do we care about it?

I have collected 3 videos that I found, which explain the concept of Binary Search Trees (BSTs) well. According to me, these are some of the best videos on the topic on the internet.

Video 1: What are BSTs used for?

Video 2: A 6 Min Summary On The Topic Of All The Imp Things To Know About BSTs

Video 3: Let’s Attend A Stanford Lecture On The Topic & Really Round Off Our Knowledge

Having seen the above videos, I am hoping you have a clear idea about what a BST is, and what it’s good for.

Prior Knowledge Sub-Topic 2: In the problem statement, the BST is represented as an array. What is up with that? How does the array correspond to the BST?

The Plan

Now, that we understand the problem, let’s talk about how we plan to solve it.

Here is the plan in simple words:

1. We will start at the root node.
2. For every node we consider, we will try to figure out what is the range of possible values this node can have.
3. For the root node, the range is from -Infinity to +Infinity. (So pretty much any number is valid)
4. If the node’s value is between the range, we say: “Hey this node’s value is valid, but I will really consider this node valid, if its left and right sub-trees are also valid!”
5. So, we then move the left child node and figure out what should be the range of that node.
6. Since it’s at the left of its parent, we know that it has to be smaller than its parent. And the min value can be the same value as the parent. The max value is one less than the parent’s value.
7. So, in this way, we get the “range” of this node.
8. Next, we move to the right of the node. Since this is on the right, the value HAS to be greater than the parent’s value. Also, it can be less than the parent nodes’ max possible value.
9. For every node we reach, we try to figure out the range it can be in and validate if it lies in that range and then if the left and right sub-trees are also valid.
10. If we find a value that is not in the range we expect, we stop and say: “The tree is not a BST!”
11. If we reach the end of the tree and everything is valid, we say: “The whole tree is valid!!“

Its A Recursion Based Solution

As you can see the problem (like all tree problems) has a very “recursive” feeling to it.

Just in case you are not super confident about what recursion is, let me try to explain it simply: Basically, to solve the problem, you need to solve many sub-problems that look exactly like the main problem but on a smaller part of the input.

Here, to validate if the whole tree is a valid BST, we need to validate the root node and if the left and right child are also valid BSTs. To do that, we need to validate if their left and right children are also valid BSTs, and to do that….. you get the point. It goes on and on and on until the tree ends.

Here are 2 videos that you can watch that might help solidify your understanding of recursion.

Let’s try to see how the plan might look as we validate a Binary Tree one step at a time:

The above is an animation of us slowly validating the BST. Below is the fully drawn tree so that you can see each node and the decided range and see if it all makes sense to you.

Below, I have changed one node in the tree, in order to produce an invalid BST. Let’s look at an animation of how the algorithm would work in that case…

Below, once again I have drawn the tree with the ranges of each node. The algo stops as soon as it finds an invalid node.

An Interactive Demo You Can Play With

Try out different binary trees and see how the algo works.

See the Pen
Validate Binary Search Tree Interactive Demo by Khoj Badami (@khoj-badami)
on CodePen.

let isThisAValidSubTree = (node, min_value_possible, max_value_possible) => {

    let nodeVal = node.val;
    if ((nodeVal <= min_value_possible) || (nodeVal >= max_value_possible)) {
        return false;
    }

    let leftChild = node.left;
    let leftChildMinValue = min_value_possible;
    let leftChildMaxValue = nodeVal;

    if (leftChild != null && isThisAValidSubTree(leftChild, leftChildMinValue, leftChildMaxValue) == false) {
        return false;
    }

    let rightChild = node.right;
    let rightChildMinValue = nodeVal;
    let rightChildMaxValue = max_value_possible;

    if (rightChild != null && isThisAValidSubTree(rightChild, rightChildMinValue, rightChildMaxValue) == false) {
        return false;
    }

    return true;
}


var isValidBST = function (root) {
    return isThisAValidSubTree(root, Number.NEGATIVE_INFINITY, Number.POSITIVE_INFINITY);
};