Validate Binary Search Tree

Threaded Binary Tree

    public boolean isValidBST(TreeNode root) {

        TreeNode prev = null, curr = root, preNode = null, curNode = null;

        while(curr != null){
            if(curr.left == null){

                preNode = curNode;
                curNode = curr;
                if(preNode != null && preNode.val >= curNode.val) return false;

                curr = curr.right;
            }else{
                // find predecessor
                prev = curr.left;
                while(prev.right != null && prev.right != curr)
                    prev = prev.right;

                if(prev.right == null){
                    prev.right = curr;
                    curr = curr.left;
                }else{
                    preNode = curNode;
                    curNode = curr;
                    if(preNode != null && preNode.val >= curNode.val) return false;

                    prev.right = null;
                    curr = curr.right;
                }
            }
        }

        return true;
    }

Recursive

    public boolean isValidBST(TreeNode root) {
        return helper(root, null, null);
    }

    private boolean helper(TreeNode root, Integer min, Integer max){
        return root == null || ((min == null || root.val > min) && (max == null || root.val < max)) && helper(root.left, min, root.val) && helper(root.right, root.val, max);
    }