098. Validate Binary Search Tree

At a Glance

• Topic: Tree
• Pattern: Analyze Pattern
• Difficulty: Medium
• LeetCode: 098

Problem Statement

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 strictly less than the node's key.
The right subtree of a node contains only nodes with keys strictly 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

Example 2:

Input: root = [5,1,4,null,null,3,6] Output: false Explanation: The root node's value is 5 but its right child's value is 4.

Constraints:

The number of nodes in the tree is in the range [1, 104].
-231 <= Node.val <= 231 - 1

Approach & Solution Steps

Use DFS with a valid range (min, max). For every node, check if it falls within the required range. Update the range for left and right children.

Optimal JS Solution

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

Edge Cases & Pitfalls

• Always consider empty or null inputs.
• Watch out for off-by-one index errors.