Skip to main content

98. Validate Binary Search Tree

mediumAsked at Microsoft

Validate Binary Search Tree is the classic Microsoft tree question that punishes the obvious-but-wrong solution: comparing each node only to its immediate children. The interviewer wants the (min, max) bounds recursion or the in-order traversal, and grades the failure case you missed.

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

Source citations

Public interview reports confirming this problem appears in Microsoft loops.

  • Glassdoor (2026-Q1)— Microsoft L60/L61 onsite reports repeatedly list Validate BST with the (min, max) twist as a 30-minute medium.
  • Blind (2025-12)— Multiple 2025 Microsoft Bing/Azure team reviews cite this as the recurring BST property check.

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 only nodes with keys greater than the node's key; both subtrees must also be 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 root node's value is 5 but its right child's value is 4.

Approaches

1. Wrong: compare each node only to its children

Naive recursion that checks node.left.val < node.val < node.right.val at each node.

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: Fails on [5,1,4,null,null,3,6] — the 3 is a valid child of 4 locally, but 3 lives in the right subtree of 5 and is less than 5. Local checks miss ancestor constraints. Useful only as the wrong answer you name and reject out loud.

2. DFS with (min, max) bounds (optimal)

Recurse with the open interval (low, high) every node must fall into. Going left tightens the upper bound; going right tightens the lower bound.

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

Tradeoff: One pass with O(h) stack. Bounds are open intervals because the BST definition is strictly less / strictly greater (no duplicates allowed in the canonical statement).

3. In-order traversal — must be strictly increasing

Do an in-order DFS and track the previous value seen. If any node is <= prev, return false.

Time
O(n)
Space
O(h)
function isValidBST(root) {
  let prev = -Infinity;
  function inorder(node) {
    if (!node) return true;
    if (!inorder(node.left)) return false;
    if (node.val <= prev) return false;
    prev = node.val;
    return inorder(node.right);
  }
  return inorder(root);
}

Tradeoff: Same complexity as the bounds approach but uses the BST in-order = sorted invariant. Both are accepted; Microsoft interviewers often ask for whichever you DIDN'T write first.

Microsoft-specific tips

Microsoft interviewers will deliberately set up the [5,1,4,null,null,3,6] case where the obvious recursion fails. Name that failure case out loud BEFORE writing code: 'a node can be locally valid but violate an ancestor constraint, so I need to pass the bounds down.' Skipping straight to the optimal without acknowledging the wrong answer is a reliability flag — they want to see you spot the trap.

Common mistakes

  • Comparing only against immediate children — fails the ancestor-constraint case.
  • Using <= or >= instead of < and > (the standard definition is strict; duplicates are NOT a valid BST).
  • Using Number.MIN_SAFE_INTEGER / Number.MAX_SAFE_INTEGER instead of -Infinity / Infinity — a leaf with value 2^31 - 1 would be wrongly rejected if the bound matches.

Follow-up questions

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

  • Recover Binary Search Tree (LC 99) — exactly two nodes are swapped, fix in O(1) space (Morris).
  • Kth Smallest Element in a BST (LC 230) — in-order traversal, stop at k.
  • Largest BST Subtree (LC 333) — same bounds trick bottom-up.

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 local-children check fail?

Because the BST property is global: every node in the left subtree (not just the left child) must be less than the node. The local check only sees one level.

Should I use the bounds approach or the in-order approach?

Either is accepted. Bounds is the more common Microsoft answer because it generalizes to many tree problems. In-order is shorter to write and clearer if you've seen the BST-in-order-is-sorted invariant.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →