Skip to main content

73. Validate Binary Search Tree

mediumAsked at Ola

Determine whether a binary tree is a valid binary search tree.

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

Problem

Given the root of a binary tree, determine if it is a valid binary search tree. A valid BST has every node's left subtree containing strictly smaller values and right subtree containing strictly larger values.

Constraints

  • Number of nodes is 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

Collect inorder values, then verify strictly increasing.

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

Tradeoff:

2. DFS with bounds

Each node must lie strictly between an open (lo, hi) range tightened by its parent's value.

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

Tradeoff:

Ola-specific tips

Ola checks that you propagate bounds rather than comparing only with the parent; tie it to validating an ordered zone-tier hierarchy invariant.

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 Ola interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →