Skip to main content

13. Validate Binary Search Tree

mediumAsked at Mercury

Check that a binary tree obeys the BST ordering property.

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

Problem

Given the root of a binary tree, determine if it is a valid BST. Every node's value must be strictly greater than all values in its left subtree and strictly less than all values in its right subtree.

Constraints

  • Node count in [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

Approaches

1. Inorder array compare

Inorder traverse into an array, then verify it is strictly ascending.

Time
O(n)
Space
O(n)
const a=[]; const dfs=n=>{ if(!n) return; dfs(n.left); a.push(n.val); dfs(n.right);}; dfs(root);
for(let i=1;i<a.length;i++) if(a[i]<=a[i-1]) return false; return true;

Tradeoff:

2. Recursive range bounds

Pass an open (lo, hi) interval down each recursion; each node must lie strictly inside it. Single pass with O(h) stack.

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

Tradeoff:

Mercury-specific tips

Mercury treats BST validation as a metaphor for tiered approval rules — every wire amount must lie strictly inside the bounds set by the approver above it in the org chart.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →