Skip to main content

63. Validate Binary Search Tree

mediumAsked at Salesforce

Determine if a binary tree is a valid BST. Salesforce uses this to test the recursive-with-bounds pattern that catches the 'check parent only' trap.

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

Source citations

Public interview reports confirming this problem appears in Salesforce loops.

  • Glassdoor (2026-Q1)— Salesforce uses BST validation in their indexed-data structures.
  • Blind (2025-12)— Recurring on Salesforce backend phone screens.

Problem

Given the root of a binary tree, determine if it is a valid binary search tree (BST). A valid BST has each left subtree containing only nodes with values less than the node's value, each right subtree containing only nodes with values greater than the node's value, and both subtrees themselves being BSTs.

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: The value 4 should be less than 5 but appears in the right subtree.

Approaches

1. Check parent-child only

Recursively check left.val < node.val < right.val.

Time
O(n)
Space
O(h)
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: WRONG. Fails on [5,1,4,null,null,3,6] because 4 < 5 violates the ancestor constraint but parent-child looks fine.

2. Pass min/max bounds through recursion

Recurse with (node, lo, hi). At each node check lo < node.val < hi. Recurse left with hi = node.val, right with lo = node.val.

Time
O(n)
Space
O(h)
function isValidBST(root) {
  function check(node, lo, hi) {
    if (!node) return true;
    if (node.val <= lo || node.val >= hi) return false;
    return check(node.left, lo, node.val) && check(node.right, node.val, hi);
  }
  return check(root, -Infinity, Infinity);
}

Tradeoff: Correct. Each recursive call narrows the valid range; ancestor constraints propagate down.

Salesforce-specific tips

Salesforce specifically tests with cases where parent-child looks fine but ancestor constraints are violated. Bonus signal: also mention the alternative inorder-traversal approach (BST iff inorder is strictly increasing), and discuss which is preferred (bounds for cleaner code; inorder for streaming).

Common mistakes

  • Only checking parent-child — fails on ancestor violations.
  • Initializing bounds to Number.MIN_VALUE/MAX_VALUE — these are NOT JS extremes; use -Infinity/Infinity.
  • Allowing equal values (`<=` should be `<` for strict BST).

Follow-up questions

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

  • Recover Binary Search Tree (LC 99) — swap exactly two nodes.
  • Inorder Successor in BST (LC 285).
  • Convert Sorted Array to BST (LC 108).

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 -Infinity / Infinity as initial bounds?

The root has no ancestor constraint, so any value is valid. -Infinity / Infinity represent 'no bound'.

Could I do this with inorder traversal?

Yes — a tree is a BST iff its inorder is strictly increasing. Walk inorder, track previous, fail on prev >= cur.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →