# Validate Binary Search Tree: Explanation + Interactive Demo

In this guide, we will look at the Leet Code problem: 98. Validate Binary Search Tree

As you probably know this is an important problem since it also features in the Blind Curated List of Top 75 LeetCode Questions to Save Your Time. This was a list created by a Facebook engineer to help people prepare for Coding Interviews. It’s a very popular list of just 75 questions from Leetcode. And if you really understand how to solve these 75 problems, in theory, you should be well prepared for coding interviews at FAANG, MANGA, or any other place you would like to apply.

Via this guide, a detailed explanation of Validate Binary Search Tree will be given. There is also an interactive demo you can play with in order to deeply understand what is going on with the problem.

## 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?

So, firstly this does not really matter in order to solve the problem on LeetCode. What I mean is that the tree had to be represented in some way, so it’s represented as an array.

If you see the code section on the leet code page, you will see something that looks like this (in the case of JS)

```/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
*     this.val = (val===undefined ? 0 : val)
*     this.left = (left===undefined ? null : left)
*     this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {boolean}
*/```

Seems like they have created some sort of “TreeNode” class and you can just call the properties:

• node.val
• node.left
• node.right

in order to access the left and right sub-trees and also the value of the current node.

However, the array representation of the BST is something you should understand. Because if you do a whiteboard coding interview you might come across this and need to make sense of it.

How an array is used to represent a BST is very well explained in this video:

As you might have learned from the above video, the following formulas can be used to represent a binary tree in the form of an array:

If a node is at index: “i”

• In the array, its left child will be at index: (2 x i)
• In the array, its right child will be at index: (2 x i) + 1
• Its parent will be at the index: Floor( i / 2 )

Look at the examples provided below in order to verify that you can understand the array representation of 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.

## A Visual Representation Of The Plan With Animations

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
on CodePen.

## An Accepted LeetCode Solution In JavaScript

At this point, I am hoping that the plan and working of the algorithm is clear. So, all that is left is the code.

The code below is an accepted solution on LeetCode. It’s fairly easy to follow and pretty short. I have tried to write it as clearly as possible.

```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);
};```

## Conclusion

With that, we come to the end of a detailed explanation of how to validate a binary search tree and solve this LeetCodee problem. I hope you found it all useful and clear.