Question4_5.java

/**
 * Implement a function to check if a binary tree is a binary search tree.
 * 
 * Time  Complexity: O(n)
 * Space Complexity: O(logn)
 */

public class Question4_5 {
    public boolean isBST(TreeNode root) {
        return recIsBST(root, null, null);
    }
    
    private boolean recIsBST(TreeNode node, Integer min, Integer max) {
        if (node == null) {
            return true;
        }
        
        if ((min == null || node.value > min) && (max == null || node.value <= max)) {
            return recIsBST(node.left, min, node.value) && recIsBST(node.right, node.value, max);
        }
        
        return false;
    }
    
    
    public static void main(String[] args) {
        Question4_5 question4_5 = new Question4_5();
        
        System.out.println(question4_5.isBST(null));
        
        TreeNode root = new TreeNode(100);
        System.out.println(question4_5.isBST(root));
        
        root.left = new TreeNode(100);
        root.right = new TreeNode(200);
        System.out.println(question4_5.isBST(root));
        
        root.left.right = new TreeNode(300);
        System.out.println(question4_5.isBST(root));
    }
}


class TreeNode {
    int value;
    TreeNode left;
    TreeNode right;
    
    public TreeNode() {
        this(0, null, null);
    }
    
    public TreeNode(int value) {
        this(value, null, null);
    }
    
    public TreeNode(int value, TreeNode left, TreeNode right) {
        this.value = value;
        this.left = left;
        this.right = right;
    }
}