# Validate Binary Search Trees

## Problem

Given a binary tree, determine if it is a valid binary search tree (BST).

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

{% hint style="info" %}
For example:

```
    5
   / \
  1   4
     / \
    3   6

Input: [5,1,4,null,null,3,6]
Output: false
Explanation: The root node's value is 5 but 
its right child's value is 4.
```

{% endhint %}

## Solution

```
class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        self.prev = None
        self.val = True
        self.helper(root, self.val)
        return self.val
    def helper(self, root, val):
        if root is None:
            return 
        self.helper(root.left, val)
        if self.prev != None:
            if self.prev.val >= root.val:
                self.val = False
                return
        self.prev = root
        self.helper(root.right, val)
            
#Time: O(log n) which is the height
#Space: O(log n) as well
```