Skip to main content

98. Validate Binary Search Tree

mediumAsked at Netflix

Determine if a binary tree is a valid BST. Netflix asks this to filter candidates who confuse 'every node is greater than its left child' (the wrong condition) with 'every node is greater than the maximum of its left subtree' (the right one).

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

Source citations

Public interview reports confirming this problem appears in Netflix loops.

  • Glassdoor (2026-Q1)— Netflix L4 onsite reports list this as the tree problem with the highest fail rate due to the parent-only check trap.
  • Blind (2025-10)— Netflix SWE writeups describe the 'min/max bounds' or 'inorder strictly-increasing' answer as the expected signal.

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: The root node's value is 5 but its right child's value is 4.

Approaches

1. Wrong: check parent-only (the trap)

Check root.left.val < root.val < root.right.val recursively. This is wrong — fails on the [5,1,4,null,null,3,6] case because 3 < 5 violates the BST property but 3 < 4 (parent) doesn't.

Time
O(n)
Space
O(h)
function isValidBSTWrong(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 isValidBSTWrong(root.left) && isValidBSTWrong(root.right);
}

Tradeoff: Demonstrate this as the wrong answer first to show you understand the trap. Then immediately fix it with bounds.

2. Recursive with min/max bounds

Pass a (low, high) bound down. Each node must satisfy low < node.val < high. Recurse left with bounds (low, node.val) and right with bounds (node.val, high).

Time
O(n)
Space
O(h) recursion
function isValidBST(root) {
  function validate(node, low, high) {
    if (!node) return true;
    if ((low !== null && node.val <= low) || (high !== null && node.val >= high)) return false;
    return validate(node.left, low, node.val) && validate(node.right, node.val, high);
  }
  return validate(root, null, null);
}

Tradeoff: Clean and explicit. The bounds propagate the full ancestry constraint — fixes the trap above.

3. Inorder traversal — strictly increasing (optimal-feel)

An inorder traversal of a BST visits values in strictly increasing order. Walk the tree iteratively and check each visit against the previous value.

Time
O(n)
Space
O(h)
function isValidBSTInorder(root) {
  const stack = [];
  let cur = root, prev = null;
  while (cur || stack.length) {
    while (cur) { stack.push(cur); cur = cur.left; }
    cur = stack.pop();
    if (prev !== null && cur.val <= prev) return false;
    prev = cur.val;
    cur = cur.right;
  }
  return true;
}

Tradeoff: Same complexity but conceptually clean — leverages the BST property that 'inorder of a BST is sorted ascending.' Many interviewers prefer this version.

Netflix-specific tips

Netflix interviewers actively look for whether you spot the parent-only-check trap. If you DON'T write the trap version first, at least mention it: 'A common mistake is to only check children against the parent, which fails on deeply violated trees.' Then go directly to the bounds version or inorder version.

Common mistakes

  • Only checking the parent-child constraint (the trap above).
  • Using `node.val < high` instead of `node.val < high` strictly — equal values violate the strict BST definition.
  • Forgetting that Node.val can equal 2^31 - 1 — initializing bounds to Number.MAX_SAFE_INTEGER works in JS; in Java you'd need Long.MIN/MAX or null sentinels.

Follow-up questions

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

  • Recover Binary Search Tree (LC 99) — two nodes were swapped, fix the tree in O(1) extra space.
  • Convert Sorted Array to BST (LC 108) — the inverse problem.
  • Largest BST Subtree — find the size of the largest BST subtree in a binary tree.

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 is the parent-only check wrong?

Because a BST's invariant is per-subtree, not per-parent. A node deep in the right subtree of root must still be greater than root, even though root isn't its direct parent. The bounds version captures the full ancestry constraint.

Which version do interviewers prefer — bounds or inorder?

Either is acceptable, but most senior interviewers slightly prefer the inorder version because it's a one-liner observation: 'inorder of a BST is sorted ascending, so check that.' The bounds version is more mechanical.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →