98. Validate Binary Search Tree 🚀
Tags: javascript, leetcode, tutorial, programming
Published: 2022-05-16 18:52:14

### Solution Developed In:
![JavaScript](https://img.shields.io/badge/javascript-%23323330.svg?style=for-the-badge&logo=javascript&logoColor=%23F7DF1E)

## The Question
For this article, we will be covering Leetcode '[98. Validate Binary Search Tree](https://leetcode.com/problems/validate-binary-search-tree/)' question. This question is rated as a **Medium** question.

Question:

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


![BST](https://assets.leetcode.com/uploads/2020/12/01/tree1.jpg)

Example:
```
Input: root = [2,1,3]
Output: true
```

## Explaining The Question
This Question is rated **Medium**. Which I believe is accurate. This question is fantastic for learning about [Binary Search Trees](https://en.wikipedia.org/wiki/Binary_search_tree) and [In order Tree Traversal](https://en.wikipedia.org/wiki/Tree_traversal). 

What we're being asked is to validate if the given Binary Search Tree is valid or not. Meaning it comply with the rules of a Binary Search Tree. Meaning all the lesser values are on the left and all the greater values are on the right.
 
Many of the solutions to this questions has you focus on the `min` and `max` values throughout the tree. This is a very common approach to solving this problem. As it checks if a min or max value is violated anywhere in the tree. Now, while this is a great approach, I think their is a simpler and better way to solve it. 

The solution I am going to explain will have transferable knowledge to lots of other issues.
1. [99. Recover Binary Search Tree](https://leetcode.com/problems/recover-binary-search-tree/)

##  Recommended Knowledge
1. [Binary Tree](https://en.wikipedia.org/wiki/Binary_tree)
2. [Depth First Search](https://en.wikipedia.org/wiki/Depth-first_search)
3. [In-order traversal](https://en.wikipedia.org/wiki/Tree_traversal#In-order)
4. [Binary Search Tree](https://en.wikipedia.org/wiki/Binary_search_tree)

## What do we know?
1. We have been given a ***Binary Search Tree***. It could be valid or not.
2. We need to validate it. 
3. Their is always going to be at least 2 nodes. 

## How we're going to do it:

Basically, what we're going to do is to traverse the Binary Tree in ***In-Order***. What this mean's is that the ***NEXT*** node we visit should always be ***greater*** than the previous node. If it isn't, then we know the tree is instantly invalid.

1. Set a `flag` to `true`, this flag will be used to let us know if the tree is valid or not. By default its always valid. Until we find a node that is less than the previous node.
2. We will declare a previous node pointer, as we're going to be keeping track of our previous node in the in-order traversal of the tree. 
3. We will perform the in-order traversal of the tree, asking at each point in the traversal, 'Is the current node less than the previous node?' If it is, then we know the tree is invalid. So we set the `flag` to `false`.
4. If no bad nodes are found, then we know the tree is valid and the flag remains untouched. 

## Big O Notation:
* Time Complexity:   *O(**n**)* | Where ***n*** is the number of nodes in our ***Binary Search Tree*** | As we're going to traverse all of the nodes within the tree.
* Space Complexity: *O(**h**)* | Where ***h*** is the height of the ***Binary Search Tree*** | Because we're going to store the height of the tree within the [Call Stack](https://en.wikipedia.org/wiki/Call_stack) due to the [in-order traversal](https://en.wikipedia.org/wiki/Tree_traversal#In-order).

' ***Could this be improved?*** ' Yes! [Morris Traversal](https://en.wikipedia.org/wiki/Tree_traversal#Morris_traversal) could do this problem in ***O(1) space complexity***. But [Morris Traversal](https://en.wikipedia.org/wiki/Tree_traversal#Morris_traversal) is tricky and tough to read. For the sake of simplicity, I don't use it here. 

## Leetcode Results:

See Submission Link: 

* Runtime: 67 ms, faster than ***94.56%*** of JavaScript online submissions for Validate Binary Search Tree
* Memory Usage: 46.8 MB, less than ***22.46%*** of JavaScript online submissions for Validate Binary Search Tree

[![LeetCode](https://img.shields.io/badge/LeetCode-000000?style=for-the-badge&logo=LeetCode&logoColor=#d16c06)](https://leetcode.com/submissions/detail/700878043/)


***

# The Solution
```
var isValidBST = function (root) {
    // This is the flag that will be returned
    // In the event we find a node that violates the BST property, we inverted the flag.
    let is_bst_valid = true;

    // We will also be tracking the previous node.
    // This will be used to check if the current node is greater than the previous node.
    // As a valid BST, the previous node must be less than the current node.
    let prev_node = new TreeNode(-Infinity, null, null);

    // We will traverse the tree in-order.
    // As a BST traversed in-order would result in something akin to a sorted array.
    // [1,2,3,4,5,6,7,8,9]
    // In the event we see something like this:
    // [1,2,3,4,*99,6,7,8,9,10]
    // We know it's not a valid BST.
    const in_order_traverse = (node) => {
        
        // Empty tree. Base case.
        if (!node || !is_bst_valid) {
            return;
        }

        // Get my left nodes.
        in_order_traverse(node.left);

        // The in order section
        // Check if the current node is greater than the previous node.
        // If not, it's a invalid tree
        if (node.val <= prev_node.val) {
            is_bst_valid = false;
        }

        // Update the previous node.
        prev_node = node;
        in_order_traverse(node.right);
    };

    in_order_traverse(root);

    // Return the flag
    return is_bst_valid;
};

```