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:

**What is a Binary Search Tree?****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:**

- We will
**start at the root node.** **For every node**we consider, we will try to**figure out what is the range of possible values**this node can have.**For the root**node, the range is from**-Infinity to +Infinity**. (So pretty much any number is valid)- 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!”** - So, we then
**move the left child node**and figure out**what should be the range of that node.** - 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. - So, in this way, we get the “range” of this node.
- 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.** **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.- If we
**find a value that is not in the range**we expect, we**stop and say: “The tree is not a BST!”** - 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 by Khoj Badami (@khoj-badami)

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.