# Determine if a BST is valid or not

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 🤷‍♂️.

![time travel shit](https://64.media.tumblr.com/51015ec638a516f7f7d353ca198a5091/tumblr_pdbo9wBAe11xd0gvgo1_1280.gifv align="left")

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

![i like it](https://media3.giphy.com/media/47yoNBN000eFEkRDGR/200.gif align="left")

The [leetcode](https://leetcode.com/problems/validate-binary-search-tree/) 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.

![1](https://i.pinimg.com/originals/fc/ca/fa/fccafa6ce178ac8c1499abff6483a131.gif align="left")

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

```js

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`.
    

---

![2](https://i.pinimg.com/originals/a3/d3/f5/a3d3f54c2726b58c269bc2ca382693ed.gif align="left")

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

```js

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`.
    

---

![3](https://i.pinimg.com/originals/5d/7c/c3/5d7cc314a06862b21765decac8654b35.gif align="left")

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

```js

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

![shrug](https://i.pinimg.com/originals/cf/ea/23/cfea23861b2353e9c725a5476731b886.gif align="left")

## Thank you for your time :D