98. Validate Binary Search Tree

Published on July 21, 2023

Question

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

A valid 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.

Example 1:

Input: root = [2,1,3]
Output: true

Algorithm

This question looks trivial at first but after implementing code1, we then realized that all the left subtree nodes should be smaller that the root not only for its left child.

So, I slightly modify the code and replace root.left.val with leftMax in Code2, then in recursion we know if there is invalid values. However, this method will have a not that good performance since each time we query the leftMax and rightMin we go through all the nodes in that subtree.

So we have code3. This code has same thoughts of code2 but implement with a different direction. Instead looking for the max and min each time, it keeps the upper bound and lower bound for each search and compare the node value along the traversal. Then we don't have to do the additional loop.

Code1

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isValidBST(TreeNode root) {
        if (root == null) return true;
        if (root.left != null && root.left.val >= root.val) {
            return false;
        }
        if (root.right != null && root.right.val <= root.val) {
            return false;
        }
        return isValidBST(root.left) && isValidBST(root.right);
    }
}

Code2

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

Code3

class Solution {
    public boolean isValidBST(TreeNode root) {
        return validate(root, null, null);
    }
    
    private boolean validate(TreeNode root, Integer floor, Integer top) {
        if (root == null) return true;
        if ((floor != null && root.val <= floor) || (top != null && root.val >= top)) {
            return false;
        }
        return validate(root.right, root.val, top) && validate(root.left, floor, root.val);
    }
}