Valid Binary Search Tree

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

  1. The left subtree of a node contains only nodes with keys less than the node’s key.
  2. The right subtree of a node contains only nodes with keys greater than the node’s key.
  3. Both the left and right subtrees must also be binary search trees.
Example :

Input : 
   1
  /  \
 2    3

Output : 0 or False


Input : 
  2
 / \
1   3

Output : 1 or True 

Return 0 / 1 ( 0 for false, 1 for true ) for this problem

Method:

Check if root's value is in range, then recursively on it's children

Solution:

Time: O(n)
Space: O(h)

/**
 * Definition for binary tree
 * class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) {
 *      val = x;
 *      left=null;
 *      right=null;
 *     }
 * }
 */
public class Solution {
    //   3
    //  2 4
    // 1 3
    public int isValidBST(TreeNode A) {
        return isValidBST(A, Integer.MIN_VALUE, Integer.MAX_VALUE);
    }
    
    private int isValidBST(TreeNode A, int min, int max) {
        if (A == null) return 1;
        if (A.val <= min || A.val >= max) {
            return 0;
        }
        int left = isValidBST(A.left, min, A.val);
        int right = isValidBST(A.right, A.val, max);
        return Math.min(left, right);        
    }
}

class Solution {
    public boolean isValidBST(TreeNode root) {
        long min = Long.MIN_VALUE;
        long max = Long.MAX_VALUE;
        return isValid(root, min, max);
    }
    
    private boolean isValid(TreeNode root, long min, long max) {
        if (root == null) return true;
        long val = (long) root.val;
        if (val <= min || val >= max) return false;
        return isValid(root.left, min, val) && isValid(root.right, val, max);
    }
}