This article is the first one in the **Random DS/Algo** series. The purpose of this series is to just act as random collection of DS/Algo problems I solved so that in future I might revisit what I explained to people on the Internet ๐คทโโ๏ธ.

This is one those questions that I always practice before an interview.

The leetcode problem statement goes like this :-

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.

There are 3 implementations that I know which can help us validate a BST.

### Inorder traversal with extra space

One of the clean features of a BST is that if you do an **inorder traversal** of the same, you get the **node values** in a sorted order.

```
function isValidBST(root){
const arr = [];
helper(root,arr);
for(let index = 0;index<arr.length-1;index++){
if(arr[index+1]<=arr[index]){
return false;
}
}
return true;
}
function helper(root,arr){
if(!root)
return;
helper(root.left,arr);
arr.push(root.val);
helper(root.right,arr);
}
```

**Approach breakdown :-**

- Initialize an empty array
`arr`

. - Call
`helper(root,arr)`

which internally does :-- Traverse the BST in
**inorder**fashion. - Push each
`root.val`

inside the`arr`

.

- Traverse the BST in
- Then we loop over the
`arr`

and for any**index**if an element is**less than or equal to**previous element, then we simply return`false`

. This is because elements should have been**strictly increasing**as per the requirements. - Otherwise, we return
`true`

.

### Inorder traversal without extra space

It's possible to do the above and exit early if there is an **invalid** BST without using extra `arr`

space.

```
var isValidBST = function(root){
const prev = helper(root,null);
return prev.isNotValid ? false : true;
}
function helper(root,prev){
if(!root)
return prev;
prev = helper(root.left,prev);
if(prev && root.val <= prev.val){
prev.isNotValid = true;
}
if(prev?.isNotValid)
return prev;
prev = root;
prev = helper(root.right,prev);
return prev;
}
```

**Approach breakdown :-**

- Let's consider
`helper(root,prev)`

first (`prev`

represents**previous node**) :-`if(!root) return prev`

- If the`root`

is`undefined`

, we return the`prev`

element.`prev = helper(root.left,prev)`

- We will first go through the**left subtree**for each`root`

to find the`prev`

element.`if(prev && root.val <= prev.val){ prev.isNotValid = true; }`

- Once we return from the**left subtree**, if`prev`

exists, we compare`root.val`

and`prev.val`

to check if current`root.val`

is**less than or equal to**`prev.val`

. If it is, we create a property on`prev`

by the name of`isNotValid`

and set it to`true`

.`if(prev?.isNotValid) return prev;`

- Next we check if this`prev.isNotValid`

exists or not and if it does then we simply return`prev`

to exit early and not further proceed for subsequent**right subtree**.`prev = root`

- This is how we set the`prev`

value to`root`

so that for next node we can use this`prev`

value for necessary comparisons.`prev = helper(root.right,prev);`

- Going through the**right subtree**for each`root`

to find the`prev`

element.`return prev;`

- It's essential to return the`prev`

to the calling function for value to reflect.

`const prev = helper(root,null);`

- Inside`isValidBST`

, we get the`prev`

element from`helper(root,null)`

.`return prev.isNotValid ? false : true;`

- If`prev.isNotValid`

exists then that means the BST is invalid and we return`false`

else we return`true`

.

### Utilizing the BST property

In BST we can say that each **node** value will be more than it's left ancestor and less than it's right ancestor for it to be valid. This is what we are going to use now :-

```
var isValidBST = function(root){
return helper(root,-Infinity,Infinity);
}
function helper(root,leftMax,rightMax){
if(!root)
return true;
if(root.val > leftMax && root.val < rightMax) {
return helper(root.left,leftMax,root.val) && helper(root.right,root.val,rightMax);
}
return false;
}
```

**Approach breakdown :-**

- Let's consider
`helper(root,prev)`

:-`if(!root) return true;`

- If the`root`

is`undefined`

we can say that the BST is valid till now.`if(root.val > leftMax && root.val < rightMax) { return helper(root.left,leftMax,root.val) && helper(root.right,root.val,rightMax); }`

- This is the core logic where we compare`root.val`

with`leftMax`

and`rightMax`

. Only if`root.val`

is**greater than**`leftMax`

and`root.val`

is**less than**`rightMax`

, we can proceed further to check for corresponding**left subtree**and**right subtree**and it's required that both of the subtrees need to return`true`

for the BST to be valid. In case of**left subtree**,`rightMax`

will change to current`root.val`

and in case of**right subtree**,`leftMax`

will change to current`root.val`

.- If the above condition fails, then we know it's not further required to check for any subsequent left or right subtree and simply return
`false`

.

- Inside
`isValidBST`

, we do`return helper(root,-Infinity,Infinity);`

and pass`leftMax`

as`-Infinity`

and`rightMax`

as`Infinity`

as initial values for our`root`

node.

Out of all the approaches the last one is really clean and I guess an interviewer might expect it. I have given interviews where the first approach was enough and interviewer didn't ask for any optimizations. But if they do, I might skip the second one and jump straight to the third one.

Also I have ignored the space taken by call stack due to recursion and well you never know I might update this article in the future with more approaches if i feel so

## Thank you for your time :D

### Did you find this article valuable?

Support **Lakshya Thakur** by becoming a sponsor. Any amount is appreciated!