Validate Binary Search Tree Medium 0 attempts
LeetCode ↗

Validate Binary Search Tree

Medium TreeBinary TreeDFS LeetCode

You're given the root of a binary tree. Determine whether it satisfies the binary search tree property: 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, not merely compared against its immediate children.

Input Format
Implement isValidBST(root). Inputs below show JavaScript function arguments; there is no stdin parsing. Trees use level-order arrays with null for missing children. The editor passes nodes with val, left, and right properties; [] becomes null.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 ยท Run Sample

Input
root = [2,1,3]
Output
true

Example 2

Input
root = [5,1,4,null,null,3,6]
Output
false
Constraints
  • 1 <= number of nodes <= 10^4
  • -2^31 <= Node.val <= 2^31 - 1
Test Cases (2)
Case 1
Args: [[2,1,3]] Expected: true
Case 2
Args: [[5,1,4,null,null,3,6]] Expected: false
Topics
TreeBinary TreeDFS

Iterative Bound Checking

Carry strict lower and upper bounds through an explicit stack. A child must satisfy every inherited ancestor bound, not just its parent comparison.

javascript
function isValidBST(root) {
  const stack=root?[[root,-Infinity,Infinity]]:[];
  while(stack.length){const [node,lo,hi]=stack.pop();if(node.val<=lo||node.val>=hi)return false;if(node.left)stack.push([node.left,lo,node.val]);if(node.right)stack.push([node.right,node.val,hi]);}
  return true;
}

Time: O(n) | Space: O(h) auxiliary space, excluding output

Saved in this browser only. Private to you.

JavaScript