#ctci

ValidBST.java

// a binary tree is a binary search tree if and only if 
// 1. all left children are less or equal to the current root and, 
// 2. all right children are larger than the current root.

// at first we may think that we can just recursion. Yeah we could.
// say for a subtree if his left child is less than the root
// and the right child is greater than root, then it's a BST.
// Well not quite. Consider the following example
//           11
//     6           16
// 4      12     10    28
// each subtree is a BST but not when they are connected
// remember, all left children and all right children
// Well how can we solve it then? Apparently we cannot just
// compare on the current level, we have to somehow pass the
// current level info as a constraint to all following levels.
// for example, when we are checking the right child of node 6,
// we should check if it is greater than 6 and <= 11
// similarly, when we check the left child of 16, we should check
// if it is <= 16 and greater than 11.
// if we write more levels, we could spot a pattern that we are constantly
// updating the range of a node should reside in based on its previous node's 
// value, if the previous node passed its own check at all.
// 
// Assume that we have the following node class
// public class Node{
//     Node left;
//     Node right;
//     int val;
// }
public class ValidBST{
    public boolean isValid(Node root){
        if(root == null) return false;
        
        return isValid(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
    }
    
    private boolean isValid(Node root, int low, int high){
        if(root == null) return true;
        
        if(root.val <= low || root.val > high) return false;
        
        return isValid(root.left, low, root.val) && isValid(root.right, root.val, high);
    }
}