**Validate Binary Search Tree**

*Recursion Method*

Tree is defined recursively. So whenever we want to solve a problem related to Tree data structure, we'd better think about *Recursion* first.

For a node in BST, it has two limitations MIN, MAX (MAX - its right node's value, MIN - its left node's value ).

For a layer of definition (node.left, node, node.right), node.left's MAX is root.val, node.right's MIN is root.val.

Thus, the recursion method is :

private boolean isValid(TreeNode root, long min, long max) {};

```
public boolean isValidBST(TreeNode root) {
return isValid(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
private boolean isValid(TreeNode root, long min, long max) {
if (root == null) return true;
if (root.val <= min || root.val >= max) return false;
return isValid(root.left, min, root.val) && isValid(root.right, root.val, max);
}
```

*Iterative Inorder Traversal Method*

Iterative Inorder Traversal can solve many problems about Tree. In this case, if we traverse the tree in-order, there should be an increasing sequence.

We set a pointer PRE to represent the previous node, and the CURRENT node should be the one we pop from the stack. PRE should always smaller than CURRENT.

```
public boolean isValidBST(TreeNode root) {
if(root == null) return true;
Stack<TreeNode> stack = new Stack<>();
TreeNode pre = null;
while(root != null || !stack.empty()){
while(root != null){
stack.push(root);
root = root.left;
}
root = stack.pop();
if (pre != null && pre.val >= root.val) return false;
pre = root;
root = root.right;
}
return true;
}
```