##### Updated on February 11, 2019

## Problem

With a binary tree as input, determine if the tree is a BST or not

## Input

`node`

: Has 3 properties`.val`

: Integer value of the node`.left`

: A pointer to another`node`

object, or`None`

if null`.right`

: A pointer to another`node`

object, or`None`

if null

- Each value in the tree is a distinct integer

## Approach

This problem is slightly tricky because it is not sufficient to simply check whether or not the left child's value is less than the parent node's value and the right child's value is greater than the parent node's value.

Specifically speaking, when traversing down the binary tree and the **direction** is changed (i.e. from *right* to *left*, or *left* to *right*), a new *boundary* is set for all child nodes.

For example, in the binary tree below, `45`

is the leaf. `45`

is indeed greater than its parent `15`

, and the subtree *only* consisting of `15`

and `45`

is considered a BST, but in the diagram, `45`

is greater than `10`

, while `10`

is less than `30`

. The BST property does not hold because \(45 \nleq 30\).

The approach then is to do the following: When we traverse down a tree, we specify the *maximum* when we go from right to left, and the *minimum* when we from left to right. Then we use this `(minimum, maximum)`

range to determine if our left/right child value satisfies the BST property.

## Solution

```
def is_valid_BST(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
def _is_valid(node, lo, hi):
if not node:
return True
valid = True
if node.left:
valid = _is_valid(node.left, lo, node.val) if node.left.val < node.val and node.left.val > lo else False
if not valid:
return False
if node.right:
valid = _is_valid(node.right, node.val, hi) if node.right.val > node.val and node.right.val < hi else False
return valid
return _is_valid(root, -float('Inf'), float('Inf'))
```