# Tree - Validate Binary Search Tree

All diagrams presented herein are original creations, meticulously designed to enhance comprehension and recall. Crafting these aids required considerable effort, and I kindly request attribution if this content is reused elsewhere.

Difficulty: Easy

PreOrder DFS, Set Min and Max Boundary

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

**Example 1:**

1
2

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

**Example 2:**

1
2
3

Input: root = [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.

## Solution

We will be solving this using PreOrder DFS. So the struture of the code will be.

```
flowchart LR
A["Base Condition"]-->B["Validate Root Node"]-->C["Traverse Left and Right Nodes"]
```

### Base Condition

The base condition is all `None`

nodes are valid, so need to return `True`

.

1
2

if not root:
return True

### Validate Root Node

Now based on the condition of the **valid BST** above,we need the boundaries for each node. As long as the node value is with in the boundary, its valid. For any left subtree, current root node value is the max value and for right substree the current root node value is the min value. So we need to pass this `min_val`

and `max_val`

to our `dfs()`

function.

1
2
3
4
5
6

def dfs(root, min_val, max_val):
if not root:
return True
if not (root.val > min_val and root.val < max_val):
return False

### Traverse

Now traverse through `left`

and `right`

children. The only logic here to set the `max_val`

and `min_val`

accordingly. In case any one children returns `False`

this function call should return `False`

as well.

1

return dfs(root.left, min_val, root.val) and dfs(root.right, root.val, max_val)

Finally we can call the `dfs()`

function for the first time by passing the `root`

node and `[-inf, +inf]`

as the `min_val`

and `max_val`

1

return dfs(root, float('-inf'), float('inf'))

## Visualization

Here is the visualization of the problem.

## Final Code

Here is the full code.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
def is_valid_bst(root:TreeNode):
def dfs(root, min_val, max_val):
if not root:
return True
if not (root.val > min_val and root.val < max_val):
return False
return dfs(root.left, min_val, root.val) and dfs(root.right, root.val, max_val)
return dfs(root, float('-inf'),float('inf'))