# Leetcode: Validate Binary Search Tree

Given the `root`

node of a tree, validate whether it is a valid **Binary Search Tree**. This is a tree where each node is unique, left children are smaller than the root and right children are greater than the root.
Because we’re dealing with a tree, there are two possible algorithms that we can use: DFS and BFS. In this case, I decided to go with a recursive DFS approach. In a simple example we see, that we need to compare the `left`

child with the `val`

of the current node. If the `left`

child is equal or greater than the value of the root node, we can return `False`

immediately and don’t need to traverse through the rest of the tree. Otherwise, we need to recursively visit the `left`

and `right`

children respectively.

`5`

. We then need to compare them to the `root`

of the tree. In this particular example, `2`

is less than `3`

and the tree is not a valid binary search tree.
To make the comparison recursively, we can pass ranges to the method in which the value has to be. We start with `[float('-inf'), float('inf')]`

and update it once we reach the first node. If we go to the left, we know that the **upper**boundary is now the nodes values. If we go to the right, we set the

**lower**boundary to the

`max(lower, node.value)`

.
Using `float('-inf')`

and `float('inf')`

respectively is a common way to initialize values in Python that need to get updated iteratively. The end result is the following code.
Runtime: 106 ms, faster than 5.15% of Python3 online submissions for Validate Binary Search Tree. Memory Usage: 16.5 MB, less than 47.01% of Python3 online submissions for Validate Binary Search Tree.