Skip to main content

68. Validate Binary Search Tree

mediumAsked at Vercel

Determine if a binary tree is a valid BST. Vercel asks this for the min/max bounds propagation pattern — same recursive shape they use to validate that nested route configurations satisfy ancestor constraints.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Vercel loops.

  • Glassdoor (2025-Q4)— Vercel platform onsite; bounds propagation expected.
  • Blind (2026-Q1)— Listed in Vercel screen pool.

Problem

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.

Constraints

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

Examples

Example 1

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

Example 2

Input
root = [5,1,4,null,null,3,6]
Output
false

Explanation: Node 4's left child 3 < 5, violates the root constraint.

Approaches

1. Compare with immediate children only (WRONG)

Check left.val < node.val < right.val recursively.

Time
O(n)
Space
O(h)
// WRONG — misses deeper violations like the 3 under 4 example.
function isValidBST(root) {
  if (!root) return true;
  if (root.left && root.left.val >= root.val) return false;
  if (root.right && root.right.val <= root.val) return false;
  return isValidBST(root.left) && isValidBST(root.right);
}

Tradeoff: Misses the case where a great-grandchild violates a great-grandparent constraint.

2. Min/max bounds propagation (optimal)

Each recursive call receives a (min, max) bound. Node is valid iff min < node.val < max. Recurse left with (min, node.val) and right with (node.val, max).

Time
O(n)
Space
O(h)
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);
}

Tradeoff: O(n), O(h) stack. The (min, max) bounds propagate the ancestor constraints down the tree. Initialize with infinity to leave the root unbounded.

Vercel-specific tips

Vercel grades the bounds-propagation approach. Bonus signal: explaining WHY the immediate-children check fails (a violation can be arbitrarily deep) and offering the inorder-traversal alternative (a valid BST has strictly increasing inorder traversal). Either solution is acceptable.

Common mistakes

  • Comparing only immediate children — fails on the 5/1/4/.../3 example.
  • Using <= and >= incorrectly — the BST requires strict inequalities.
  • Forgetting infinity initialization — the root has no bounds.

Follow-up questions

An interviewer at Vercel may pivot to one of these next:

  • Recover Binary Search Tree (LC 99) — two nodes swapped.
  • Inorder traversal alternative — produces sorted output iff valid BST.
  • Kth smallest in BST (LC 230).

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why min/max bounds?

BST property is transitive: a left descendant must be less than EVERY ancestor on the right-going path. The bounds carry that transitive constraint down.

Inorder traversal alternative?

A valid BST's inorder traversal is strictly increasing. Walk inorder; if any consecutive pair violates ordering, invalid. Same O(n) time, easier to extend (e.g., to detect swapped pairs for LC 99).

Practice these live with InterviewChamp.AI

Drill Validate Binary Search Tree and other Vercel interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →