Hi!

I wanted to share my answer to a really cool problem I came across on leetcode. I want to do it a bit differently, I want to first share a sort of pseudocode/steps for anyone kind of stuck that wouldn't want the answer right away.

### - The problem

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 thanthe node's key.- The right subtree of a node contains only nodes with keys
greater thanthe node's key.- Both the left and right subtrees must also be binary search trees.

**This is what a binary search tree should look like**

Anything on the left must be less than the parent and anything on the right must be bigger than the parent.

### - Thoughts / Questions

Some things to keep in mind if you were asked this during an interview.

###### Questions

- What would the output need to be (this case leetcode gives it to use and it is a boolean. )
- I would if possible draw out a BST and a tree to confirm the question.
- What are we given in the function. ( head, value, left, right?)

###### Thought process

- For this Problem I want to first traverse the tree inOrder and add the values to an array. By doing this we will have all the values in order.
- Next I want to run a loop to check if the value at our current index is bigger or equal to the next value. if it is we return false because we know this is not a valid BST.

With InOrder Our output will be in order. Meaning we are grabbing the lowest value first and working our way up.

- Looking at the picture above you can see if a value before hand is bigger there is no way this is a valid BST.

### - Steps

This is going to be a more indepth walkthrough of our problem.

- In our leetcode problem we are only given access to the root.

- First We need to traverse our given tree using DFS Inorder.
- Create a variable to store the values of nodes that we visited.
- Write a helper function called traverse which accepts a node.
- If the node has a left property, call the helper function with the left property on the node.
- Push the values of the node to the variable that stores the values.
- If the node has a right property, call the helper function with the right property on the node.

- Invoke the helper function with the given root.
- Using the visited array we can write a for loop on the length of the array.
- In the loop we can write an if statement to check if the value at our current index is bigger than the next value if it is we can return false.
- after the loop runs we can return true because this means no value beforehand was bigger.

### - The code

```
const isValidBST = root => {
let results = [];
const traverse = tree =>{
if(!tree) return null
if(tree.left) traverse(tree.left)
results.push(tree.val)
if(tree.right) traverse(tree.right)
}
traverse(root)
for(let i = 0; i < results.length; i++){
if(results[i] >= results[i + 1]) return false
}
return true
};
```

Hope this was helpful!

## Top comments (0)