Validate Binary Search Tree

MediumTree BST DFS Recursion

A storage engine keeps an in-memory index as a binary search tree. After a crash it must verify that the index is still intact before trusting it. The index is intact when, for every node:

every value in the node's left subtree is strictly smaller than the node's value, and
every value in its right subtree is strictly larger.

Given the root, return true if the whole tree follows this rule and false otherwise. Duplicate values therefore make the index invalid, while an empty tree is valid. Node values can be as large as 2^31 - 1 and as small as -2^31.

Example 1

Input: root = [50,30,70,20,40,60,80]
Output: true

Explanation: Every left subtree holds smaller keys and every right subtree holds larger keys.

Example 2

Input: root = [50,30,70,20,55]
Output: false

Explanation: 55 is a fine right child of 30, but it sits in the left subtree of 50 while being larger than 50.

Example 3

Input: root = [7,null,7]
Output: false

Explanation: A right child equal to its parent breaks the "strictly larger" rule.

Constraints

The tree has at most 10^4 nodes.
Node values can be any 32-bit signed integer.

💡 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