### Solution Developed In:

## The Question

For this article, we will be covering Leetcode '98. 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 BSTis 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.

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 and In order 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.

## Recommended Knowledge

## What do we know?

- We have been given a
. It could be valid or not.*Binary Search Tree* - We need to validate it.
- 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

**node we visit should always be**

*NEXT***than the previous node. If it isn't, then we know the tree is instantly invalid.**

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

. - 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**)*| Whereis the number of nodes in our*n*| As we're going to traverse all of the nodes within the tree.*Binary Search Tree* - Space Complexity:
*O(**h**)*| Whereis the height of the*h*| Because we're going to store the height of the tree within the Call Stack due to the in-order traversal.*Binary Search Tree*

' ** Could this be improved?** ' Yes! Morris Traversal could do this problem in

**. But Morris Traversal is tricky and tough to read. For the sake of simplicity, I don't use it here.**

*O(1) space complexity*## Leetcode Results:

See Submission Link:

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

# 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;
};
```

## Top comments (0)