98. Validate Binary Search Tree!

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isValidBST(TreeNode root) {
        // use tack for iterative inorder trasversal
        Stack<TreeNode> memo = new Stack<>();
        Integer prev = null;
        while(root!=null || !memo.isEmpty()){
            // remember: stack.isEmpty();
            while(root!=null){
                memo.push(root);
                root = root.left;
            }
            root = memo.pop();
            if(prev != null && root.val<=prev) return false;
            prev = root.val;
            root = root.right;
        }
        return true;
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    // use reference type to avoid corner case of max or min int value;
    Integer prev = null;
    public boolean isValidBST(TreeNode root) {
        return inOrderSearch(root);
    }
    
    private boolean inOrderSearch(TreeNode node){
        if(node==null) return true;
        
        if(!inOrderSearch(node.left)){
            return false;
        }
        
        if(prev == null || node.val>prev){
            prev = node.val;
            return inOrderSearch(node.right);
        }else{
            return false;
        }
    }
}