Skip to main content

98. Validate Binary Search Tree

mediumAsked at HubSpot

HubSpot asks Validate BST to test whether you understand the BST property beyond the naive 'left < root < right' check — they want to see you propagate valid range bounds through the recursion, a pattern that reflects the kind of constraint-passing thinking their backend engineers apply daily.

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

Source citations

Public interview reports confirming this problem appears in HubSpot loops.

  • Glassdoor (2026-Q1)— HubSpot SWE interview reports list Validate BST as a core tree problem probing range-bound propagation.
  • Blind (2025-11)— HubSpot candidates frequently cite Validate BST as an onsite problem that trips up candidates who use the naive local comparison.

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 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.

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

Explanation: Node 2: left child 1 < 2, right child 3 > 2. Valid BST.

Example 2

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

Explanation: Node 4 is the right child of 5, but 4 < 5 — violates the BST property.

Approaches

1. Recursive range validation

Pass min and max bounds down the tree. At each node, check that its value falls strictly within (min, max). Left subtree gets max = node.val; right subtree gets min = node.val.

Time
O(n)
Space
O(h) where h is tree height
function isValidBST(root, min = -Infinity, max = Infinity) {
  if (root === null) 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) time, O(h) space for the call stack. The range propagation is the key insight — initializing min = -Infinity and max = Infinity as defaults makes the API clean. This is the canonical expected answer.

2. In-order traversal (iterative)

A BST's in-order traversal produces a strictly increasing sequence. Traverse in-order iteratively and verify each value is strictly greater than the previous.

Time
O(n)
Space
O(h)
function isValidBST(root) {
  const stack = [];
  let prev = -Infinity;
  let curr = root;
  while (curr !== null || stack.length > 0) {
    while (curr !== null) {
      stack.push(curr);
      curr = curr.left;
    }
    curr = stack.pop();
    if (curr.val <= prev) return false;
    prev = curr.val;
    curr = curr.right;
  }
  return true;
}

Tradeoff: Iterative and avoids recursion-stack overflow for skewed trees. The in-order invariant is elegant and easy to explain. However, it processes the entire tree even if the violation is near the root; the range approach can short-circuit earlier.

HubSpot-specific tips

Lead with the common mistake to show awareness: 'The naive approach — check only left < root < right locally — fails for trees like [5, 1, 4] where 4 is a right child but violates the constraint relative to the grandparent 5.' Then present the range propagation. HubSpot interviewers often follow up with 'can you do it iteratively?' — have the in-order traversal ready. Handle Integer.MIN_VALUE / Integer.MAX_VALUE as node values — always use -Infinity/Infinity as initial bounds.

Common mistakes

  • Checking only the immediate left and right children instead of propagating range bounds — classic naive BST validation trap.
  • Using -2^31 and 2^31-1 as initial bounds instead of -Infinity/Infinity — a node with value -2^31 would fail the left bound check.
  • Not handling the strictly less/greater requirement — using <= instead of < in the range check allows duplicate values, which is not a valid BST.
  • Returning true for null nodes without propagating the validity of the path — null nodes are trivially valid; the check must happen at non-null nodes.

Follow-up questions

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

  • Kth Smallest Element in a BST (LC 230) — in-order traversal counting to k.
  • Lowest Common Ancestor of a BST (LC 235) — exploit BST ordering for O(h) LCA.
  • How would you validate a BST if the tree is represented as a serialized array?

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 does the naive left < root < right check fail?

It validates only the local relationship but not the global invariant. A node deep in the right subtree might be less than its great-grandparent, which local comparison misses entirely.

Why use -Infinity and Infinity as initial bounds?

Node values can be any integer including INT_MIN and INT_MAX. Using -Infinity/Infinity ensures no valid root value is falsely rejected by the initial bound check.

Is the in-order approach O(n) even if the violation is at the root's right child?

In the worst case yes — the in-order traversal visits the entire left subtree first. The range propagation approach short-circuits at the first violation, potentially processing far fewer nodes.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →