Overview

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

A valid BST is defined as:

• The left subtree of a node contains only nodes with values strictly less than the node's value.
• The right subtree contains only nodes with values strictly greater than the node's value.
• Both subtrees must also be valid BSTs.

Implement isValidBST(root).

Constraints

• Tree nodes have shape { val, left, right }.
• Node values are integers (may be negative).
• An empty tree (null) is a valid BST.
• A single node is a valid BST.
• Must validate the entire subtree constraint — not just immediate children.

Examples

//   2
//  / \\
// 1   3
isValidBST(root);  // true

//   5
//  / \\
// 1   4
//    / \\
//   3   6
isValidBST(root);  // false — 3 is in right subtree of 5 but < 5… wait, 
//                    4 is in the right subtree of 5 but 4 < 5, so invalid.

//   1
//  / \\
// 1   1
isValidBST(root);  // false — duplicates not allowed

Notes

• The naive approach of checking only immediate children is wrong — a node in the right subtree could violate the root's constraint while satisfying its parent's.
• Pass down min/max bounds: each recursive call narrows the valid range for that subtree.
• Alternatively, an in-order traversal should produce a strictly increasing sequence.

Solution

function isValidBST(root) {
  function validate(node, min, max) {
    if (!node) return true;
    if (node.val <= min || node.val >= max) return false;
    return validate(node.left, min, node.val) && validate(node.right, node.val, max);
  }
  return validate(root, -Infinity, Infinity);
}

Resources

• Validate Binary Search Tree — LeetCode
• Binary Search Tree — Wikipedia