[LeetCode] Validate Binary Search Tree (Java)

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.

Analysis

I have been asked this question in an interview. In fact, this problem is not so difficult.

Algorithm 1: We have known what is a BST, so we can write a function to find the maximum value in the left subtree of root node, and the minimum value in the right subtree of root node, and compare them with value of root. We need to continue doing this for each node in the tree. But every time we find the maximum value of minimum value will costs $O(n)$, and this algorithm will cost $O(n^2)$ because we need to do this for every node, which is not efficient.

Algorithm 2: For a node root, we know that all nodes in the left subtree is smaller than the value of root. We can pass this value to the left subtree, checking if the value of its left child is smaller than this value. Then we will update this passing value to the value of left child and keep passing it to next level. For the right subtree, we need to make sure that all values in the right subtree is larger than the value of root. In conclusion, we should pass two values, which is min and max, to the next level, and compare the value of nodes. Update the min and max, and pass it to next level until we reach the leaf node.

Algorithm 3: The in-order traverse can helps us. Doing a in-order traverse on a BST, the output will be a increasing sequence.

Code

Algorithm 2

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

public class Solution {

public boolean isValidBST(TreeNode root) {

return isValidBST(root, Integer.MAX_VALUE, Integer.MIN_VALUE);

}

public boolean isValidBST(TreeNode root, int max, int min) {

if (root == null)

return true;

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

return false;

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

}

There is a small bug in this code. If the smallest node has the value Integer.MIN_VALUE or the largest node has the value Integer.MAX_VALUE, it won’t work.

Algorithm 3

public class Solution {
    public boolean isValidBST(TreeNode root) {
        return inorderTraverse(root);
    }
    
    TreeNode prev = null;
    public boolean inorderTraverse(TreeNode root) {
        if (root == null)
            return true;
        if (!inorderTraverse(root.left))
            return false;
        if (prev != null) {
            if (root.val <= prev.val)
                return false;
        }
        prev = root;
        if (!inorderTraverse(root.right))
            return false;
        return true;
    }
}

public class Solution {

public boolean isValidBST(TreeNode root) {

return inorderTraverse(root);

}

TreeNode prev = null;

public boolean inorderTraverse(TreeNode root) {

if (root == null)

return true;

if (!inorderTraverse(root.left))

return false;

if (prev != null) {

if (root.val <= prev.val)

return false;

}

prev = root;

if (!inorderTraverse(root.right))

return false;

return true;

}

Complexity

The complexity of algorithm 2 and 3 is $O(n)$, since we only visit each node once.