# Validate [[bst|Binary Search Tree]]
https://leetcode.com/problems/validate-binary-search-tree/
## Solution 1: Recursion with Range
```python
def helper(root, lo=-math.inf, hi=math.inf):
return (
lo < root.val < hi and
helper(root.left, lo, root.val) and
helper(root.right, root.val, hi)
) if root else True
return helper(root)
```
## Solution 2: Iteration with Range
```python
queue = [(root, -math.inf, math.inf)]
while queue:
root, lo, hi = queue.pop(0)
if not lo < root.val < hi:
return False
if root.left:
queue.append((root.left, lo, root.val))
if root.right:
queue.append((root.right, root.val, hi))
return True
```
- Time complexity: $O(N)$, as each node is inserted and popped from the queue once.
- Space complexity: $O(N/2) = O(N)$, the queue is as large as the total number of leaves.
## Solution 3: Recursive [[inorder|Inorder Traversal]]
Utilize the fact that the in-order traversal of a BST is ascending.
```python
traversal = traverse(root)
return len(traversal) <= 1 or eval('<'.join(str(val) for val in traversal))
```
Alternatively:
```python
return all(x < y for x, y in zip(traversal, traversal[1:]))
```
## Solution 4: Iterative In-Order Traversal
With iteration, we can terminate the iteration once the in-order traversal is not strictly increasing.
```python
stack, prev = [], -math.inf
while stack or root:
while root:
stack.append(root)
root = root.left
root = stack.pop()
if root.val <= prev: # the left-most leave is smallest in BST
return False
prev = root.val
root = root.right
return True
```