Note that it is not enough to write a recursive function that just checks if the left and right nodes of each

node are less than and greater than the current node (and calls that recursively). You need to make sure that all the nodes of the subtree starting at your current node are within the valid range of values allowed

by the current node's ancestors. Therefore you can solve this recursively by writing a helper function that accepts a current node, the smallest allowed value, and the largest allowed value for that subtree.

Example for this:-

```
boolean isValid(Node root) {
return isValidHelper(root, Integer.MIN_VALUE,
Integer.MAX_VALUE);
}
boolean isValidHelper(Node curr, int min, int max) {
if (curr.left != null) {
if (curr.left.value < min ||
!isValidHelper(curr.left, min, curr.value))
return false;
}
if (curr.right != null) {
if (curr.right.value > max ||
!isValidHelper(curr.right, curr.value, max))
return false;
}
return true;
}
```

The running time of this algorithm is O(n).