Validate Binary Search Tree

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 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.
confused what “{1,#,2,3}” means? > read more on how binary tree is serialized on OJ.

这道题和之前一道找BST里面swap元素的题一样,只要in order traversal,用一个largest的值来追踪当前为止最大的值。注意BST不允许有重复元素,所以要判断前一个值大于或等于当前值,那么当前的BST就不valid了。

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    int largest = Integer.MIN_VALUE;
    public boolean isValidBST(TreeNode root) {
        if (root == null)
            return true;
        if (isValidBST(root.left) == false)
            return false;
        if (largest >= root.val)
        {
            return false;
        }
        largest = root.val; // why is this line? think about it!
        return isValidBST(root.right);
    }
}

Second Submission:

The same idea works for all the BST, use a pointer to track the previous largest number, and recursively goes to the next

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    TreeNode last;
    public boolean isValidBST(TreeNode root) {
        if (root == null)
            return true;
        if (isValidBST(root.left)){
            if (last != null)
                if (last.val >= root.val)
                    return false;
        }
        else
            return false;
        last = root;
        return (isValidBST(root.right));
    }
}

Another approach from top down, pass a min and max value and check if root is in right range or not, simpler logic

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean isValidBST(TreeNode root) {
        return isBST(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
    }
    
    public boolean isBST(TreeNode root, int min, int max) {
        if (root == null)
            return true;
        if (root.val <= min || root.val >= max)
            return false;
        return isBST(root.left, min, root.val) && isBST(root.right, root.val, max);
    }
}

One thought on “Validate Binary Search Tree

  1. Pingback: BST serialization and deserialization | Hello World

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s