Leetcode #98 (validate binary search tree)

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

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

1. What would the output need to be (this case leetcode gives it to use and it is a boolean. )
2. I would if possible draw out a BST and a tree to confirm the question.
3. 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.

1. First We need to traverse our given tree using DFS Inorder.
2. Create a variable to store the values of nodes that we visited.
3. 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.
4. Invoke the helper function with the given root.
5. Using the visited array we can write a for loop on the length of the array.
6. 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.
7. 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!