Validate Binary Search Tree

Medium Validate Binary Search Tree

24%

Accepted

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

Assume a BST is defined as follows:

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

Have you met this question in a real interview? 

Yes

Example

An example:

  2
 / \
1   3
   /
  4
   \
    5

The above binary tree is serialized as {2,1,3,#,#,4,#,#,5} (in level order).

/**

 * 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) {

        // write your code here

        return _isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);

    }

    

    private boolean _isValidBST(TreeNode root, long min, long max){

        if(root == null) return true;

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

        return _isValidBST(root.left, min, root.val) && _isValidBST(root.right, root.val, max);

    }

}