42. Validate Binary Search Tree

Given the root of a binary tree, return true if it is a valid binary search tree (BST) and false otherwise.

A BST requires, for every node:

every value in its left subtree is strictly less than the node's value,
every value in its right subtree is strictly greater than the node's value.

Duplicates are therefore not allowed. The empty tree counts as a valid BST. Watch out: node values can be as large as 2^31 - 1 and as small as -2^31.

Example 1

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

Example 2

Input: root = [8,3,10,null,9]
Output: false

Explanation: 9 is a valid right child of 3, but it sits in the left subtree of 8 and is larger than 8.

Example 3

Input: root = [1,1]
Output: false

Explanation: Equal values break the "strictly less" rule.

Constraints

The number of nodes is in the range [0, 10^4]
-2^31 <= Node.val <= 2^31 - 1

💡 Hint 1

Comparing each node only with its direct children is not enough. The second example passes that check and is still invalid.

💡 Hint 2

Every node must lie inside an open interval (low, high) inherited from its ancestors. Going left tightens high, going right tightens low.

💡 Hint 3

In Java, start the bounds outside the int range (for example with long), or use null for "no bound", so that Integer.MIN_VALUE and Integer.MAX_VALUE nodes are handled correctly.

Try it yourself first ✎

Solutions stick better after a real attempt. Peek when you're ready.

Approach

Carry an open interval (low, high) down the tree. The root may hold any value. When you step into a left child, the parent's value becomes the new high; when you step right, it becomes the new low. A node outside its interval (including equal to a bound) makes the tree invalid. In Java the bounds are longs starting at Long.MIN_VALUE/Long.MAX_VALUE, so nodes holding Integer.MIN_VALUE or Integer.MAX_VALUE are not mistaken for violations. An equivalent approach: an in-order traversal of a BST is strictly increasing, so compare each value with the previous one.

Time O(n)Space O(h), where h is the tree height

function isValidBST(root) {
  const check = (node, low, high) => {
    if (!node) return true;
    if (node.val <= low || node.val >= high) return false;
    return check(node.left, low, node.val) && check(node.right, node.val, high);
  };
  return check(root, -Infinity, Infinity);
}

class Solution {
    public boolean isValidBST(TreeNode root) {
        return check(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    private boolean check(TreeNode node, long low, long high) {
        if (node == null) return true;
        if (node.val <= low || node.val >= high) return false;
        return check(node.left, low, node.val) && check(node.right, node.val, high);
    }
}

/**
 * Definition for a binary tree node (provided):
 * function TreeNode(val, left, right) { this.val = val ?? 0; this.left = left ?? null; this.right = right ?? null; }
 *
 * @param {TreeNode} root
 * @return {boolean}
 */
function isValidBST(root) {

}

Ctrl/⌘ + ' run · Ctrl/⌘ + Enter submit