Validate Binary Search Tree Solutions in Java

// Source : https://oj.leetcode.com/problems/validate-binary-search-tree/
// Inspired by : http://www.jiuzhang.com/solutions/validate-binary-search-tree/
// Author : Lei Cao
// Date   : 2015-10-06



package validateBinarySearchTree;

public class validateBinarySearchTree {
    public boolean isValidBST(TreeNode root) {
        return isBSTTraversal(root) && isBSTDivideAndConquer(root);
    }

    // Solution 1: Traversal
    // The inorder sequence of a BST is a sorted ascending list
    private int lastValue = 0; // the init value of it doesn't matter.
    private boolean firstNode = true;
    public boolean isBSTTraversal(TreeNode root) {
        if (root == null) {
            return true;
        }

        if (!isValidBST(root.left)) {
            return false;
        }

        // firstNode is needed because of if firstNode is Integer.MIN_VALUE,
        // even if we set lastValue to Integer.MIN_VALUE, it will still return false
        if (!firstNode && lastValue >= root.val) {
            return false;
        }

        firstNode = false;
        lastValue = root.val;

        if (!isValidBST(root.right)) {
            return false;
        }

        return true;

    }

    // Solution 2: divide && conquer
    private class Result {
        int min;
        int max;
        boolean isBST;
        Result(int min, int max, boolean isBST) {
            this.min = min;
            this.max = max;
            this.isBST = isBST;
        }
    }

    public boolean isBSTDivideAndConquer(TreeNode root) {
        return isBSTHelper(root).isBST;
    }

    public Result isBSTHelper(TreeNode root) {
        // For leaf node's left or right
        if (root == null) {
            // we set min to Integer.MAX_VALUE and max to Integer.MIN_VALUE
            // because of in the previous level which is the leaf level,
            // we want to set the min or max to that leaf node's val (in the last return line)
            return new Result(Integer.MAX_VALUE, Integer.MIN_VALUE, true);
        }

        Result left = isBSTHelper(root.left);
        Result right = isBSTHelper(root.right);

        if (!left.isBST || !right.isBST) {
            return new Result(0,0, false);
        }

        // For non-leaf node
        if (root.left != null && left.max >= root.val
                && root.right != null && right.min <= root.val) {
            return new Result(0, 0, false);
        }

        return new Result(Math.min(left.min, root.val),
                Math.max(right.max, root.val), true);
    }
}

/// Source : https://leetcode.com/problems/validate-binary-search-tree/description/
/// Author : liuyubobobo
/// Time   : 2018-05-22

import java.util.ArrayList;

/// Using inOrder traverse
/// Store all elements in an ArrayList
///
/// Time Complexity: O(n)
/// Space Complexity: O(n)
class Solution {

    public boolean isValidBST(TreeNode root) {

        ArrayList<Integer> list = new ArrayList<>();
        inOrder(root, list);
        for(int i = 1 ; i < list.size() ; i ++)
            if(list.get(i - 1) >= list.get(i))
                return false;
        return true;
    }

    private void inOrder(TreeNode node, ArrayList<Integer> list){

        if(node == null)
            return;

        inOrder(node.left, list);
        list.add(node.val);
        inOrder(node.right, list);
    }
}

/// Source : https://leetcode.com/problems/validate-binary-search-tree/description/
/// Author : liuyubobobo
/// Time   : 2018-05-22

/// Recursive test
/// Time Complexity: O(n)
/// Space Complexity: O(h)
class Solution2 {

    public boolean isValidBST(TreeNode root) {

        return isValidBST(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
    }

    private boolean isValidBST(TreeNode node, int min, int max){

        if(node == null)
            return true;

        if(node.val < min || node.val > max)
            return false;

        if(node.left != null && node.left.val >= node.val)
            return false;

        if(node.right != null && node.right.val <= node.val)
            return false;

        return isValidBST(node.left, min, node.val - 1) &&
                isValidBST(node.right, node.val + 1, max);
    }

    public static void main(String[] args){

        TreeNode root = new TreeNode(-2147483648);
        root.left = new TreeNode(-2147483648);

        System.out.println((new Solution2()).isValidBST(root));
    }
}

/// Source : https://leetcode.com/problems/validate-binary-search-tree/description/
/// Author : liuyubobobo
/// Time   : 2018-12-16


import java.util.Stack;

/// Non-Recursion Solution for Recursion thinking
/// Time Complexity: O(n)
/// Space Complexity: O(h)
public class Solution3 {


    public boolean isValidBST(TreeNode root) {

        if(root == null) return true;

        Stack<TreeNode> stack = new Stack<>();
        Stack<Integer> lower = new Stack<>();
        Stack<Integer> upper = new Stack<>();

        stack.push(root);
        lower.push(Integer.MIN_VALUE);
        upper.push(Integer.MAX_VALUE);
        while(!stack.empty()){
            TreeNode cur = stack.pop();
            int left = lower.pop();
            int right = upper.pop();

            if(cur.val < left || cur.val > right)
                return false;

            if(cur.right != null){
                if(cur.right.val <= cur.val) return false;
                stack.push(cur.right);
                lower.push(cur.val + 1);
                upper.push(right);
            }

            if(cur.left != null){
                if(cur.left.val >= cur.val) return false;
                stack.push(cur.left);
                lower.push(left);
                upper.push(cur.val - 1);
            }
        }
        return true;
    }
}

/// Source : https://leetcode.com/problems/validate-binary-search-tree/description/
/// Author : liuyubobobo
/// Time   : 2018-05-22

/// InOrder traverse
/// validate during the traversing
///
/// Time Complexity: O(n)
/// Space Complexity: O(h)
public class Solution4 {

    private Integer pre = null;

    public boolean isValidBST(TreeNode root) {

        return inOrder(root);
    }

    private boolean inOrder(TreeNode node){

        if(node == null)
            return true;

        if(!inOrder(node.left))
            return false;

        if(pre != null && node.val <= pre)
            return false;
        pre = node.val;

        if(!inOrder(node.right))
            return false;

        return true;
    }
}

/// Source : https://leetcode.com/problems/validate-binary-search-tree/description/
/// Author : liuyubobobo
/// Time   : 2018-12-16

/// Morris InOrder traversal
/// Attention: you can not change the give Tree structure in Leetcode,
/// So try to return result early will lead to RE :-)
///
/// Time Complexity: O(n)
/// Space Complexity: O(1)
public class Solution5 {

    private boolean flag;
    private int pre;

    public boolean isValidBST(TreeNode root) {

        flag = false;
        pre = -1;

        TreeNode cur = root;
        boolean res = true;
        while(cur != null){

            if(cur.left == null){
                if(!process(cur.val)) return false;
                cur = cur.right;
            }
            else{
                TreeNode prev = cur.left;
                while(prev.right != null && prev.right != cur)
                    prev = prev.right;

                if(prev.right == null){
                    prev.right = cur;
                    cur = cur.left;
                }
                else{
                    prev.right = null;
                    if(!process(cur.val))
                        return false;
                    cur = cur.right;
                }
            }
        }
        return true;
    }

    private boolean process(int v){

        if(flag && pre >= v)
            return false;

        flag = true;
        pre = v;
        return true;
    }
}