# Recursion || Iterative Inorder Traversal

• 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;
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.