## DEV Community is a community of 698,942 amazing developers

We're a place where coders share, stay up-to-date and grow their careers. # Determine if a BST is valid or not Lakshya Thakur
I like to have creative insights towards my subjects and apply my engineering skills for problem solving.
Originally published at blog.lakbychance.com ・4 min read

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 :-

1. Initialize an empty array `arr`.
2. Call `helper(root,arr)` which internally does :-
1. Traverse the BST in inorder fashion.
2. Push each `root.val` inside the `arr`.
3. 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.
4. 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 :-

1. Let's consider `helper(root,prev)` first (`prev` represents previous node) :-
1. `if(!root) return prev` - If the `root` is `undefined` , we return the `prev` element.
2. `prev = helper(root.left,prev)` - We will first go through the left subtree for each `root` to find the `prev` element.
3. ```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`.
4. `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.
5. `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.
6. `prev = helper(root.right,prev);` - Going through the right subtree for each `root` to find the `prev` element.
7. `return prev;` - It's essential to return the `prev` to the calling function for value to reflect.
2. `const prev = helper(root,null);` - Inside `isValidBST`, we get the `prev` element from `helper(root,null)`.
3. `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 :-

1. Let's consider `helper(root,prev)`:-
1. `if(!root) return true;` - If the `root` is `undefined` we can say that the BST is valid till now.
2. ```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`.
3. 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`.
2. 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 