3.5 Validate Binary Search Tree

Assume a BST is defined as follows:

• The left subtree of a node contains only nodes with keys less than the node's key.
• The right subtree of a node contains only nodes with keys greater than the node's key.
• Both the left and right subtrees must also be binary search trees.

Logical Steps

1. Define a return type which carries the maximum value allowed in left tree, minimum value allowed in right tree, and isBST or not
2. Divide: recursively check left and right tree. If tree is not null and leftMax >= root val or rightMin >= root val, this current tree is not a valid BST, set isBST in return to be false
3. Update: the max value in left tree depends on root value and left max value in right tree. By doing this comparison we drop the case where right tree has value < left tree. For the same reason, min value in right tree depends on root value and right max value of left tree
4. Conquer: left and right isBST and current return type isBST

Code Template

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */
public class Solution {
    /**
     * @param root: The root of binary tree.
     * @return: True if the binary tree is BST, or false
     */
    public boolean isValidBST(TreeNode root) {
        ReturnType rst = helper(root);
        return rst.isBST;
    }

    public ReturnType helper(TreeNode root) {
        ReturnType tmp = new ReturnType(true, Integer.MIN_VALUE, Integer.MAX_VALUE);

        if (root == null)
            return tmp;

        ReturnType left = helper(root.left);
        ReturnType right = helper(root.right);

        // compare root with left tree
        // remember to put root.left != null here to avoid comparion
        // when tree only has root (initial max and min will be equal
        // in root and empty nodes)
        if (root.left!= null && left.max >= root.val){
            tmp.isBST = false;
        }

        // compare root with right tree
        if (root.right != null && right.min <= root.val) {
            tmp.isBST = false;
        }

        /** refresh
         * max value depends on max of right tree and current val
         * left tree cannot have greater value than any element in right tree
         */ 
        tmp.max = Math.max(right.max, root.val);

        /** refresh
         * min value depends on min of left tree and current val
         * right tree cannot have smaller value than any element in left tree
         */
        tmp.min = Math.min(left.min, root.val);

        // current, left, right has to be both BST
        tmp.isBST = tmp.isBST && left.isBST && right.isBST;

        return tmp;
    }
}

class ReturnType{
    boolean isBST;
    int max;
    int min;

    ReturnType(){};

    ReturnType(Boolean isBST, int max, int min) {
        this.isBST = isBST;
        this.max = max;
        this.min = min;
    }
}

Common Mistakes

1. Instead of passing max and min in return type, put it in recursion parameter: parent nodes will have to get max and min value from child nodes, new return type is necessary
2. Refresh: max of current node depend on left tree, or max of current node depend on right tree: confused by variable name

3. See following code:

   // compare root with left tree
        ReturnType tmp = new ReturnType(true, Integer.MIN_VALUE, Integer.MAX_VALUE);
   
        /** this is a mistake example
        * if there is not left!= null check here
        * when tree only have a root
        * null left node will return max=Integer.MIN_VALUE
        * which is equal to current max value
        * and return false
        */
        if (left.max >= root.val){
            tmp.isBST = false;
        }
   
        // same thing here
        if (right.min <= root.val) {
            tmp.isBST = false;
        }