noodleProblems/
Validate Binary Search Tree
#103

Validate Binary Search Tree

AlgorithmmediumTreeDepth First SearchBinary Search TreeBinary Tree

Given the root of a binary tree, return true if it is a valid **binary search tree**.

A tree is a valid BST when, for *every* node, all values in its left subtree are strictly less than the node's value and all values in its right subtree are strictly greater. The constraint is global, not just parent-to-child: a node deep in a right subtree still must respect every ancestor's bound.

The tree is given as a level-order array where null marks a missing child: [2, 1, 3] is root 2 with children 1 and 3.

Example cases

  • valid
    in root = [2,1,3]123
    out true
    1 < 2 < 3.
  • right child too small
    in root = [5,1,4,null,null,3,6]15346
    out false
    4 is in 5's right subtree but 4 < 5 violates the global bound; also 3 < 5.
  • single node
    in root = [1]1
    out true

Constraints

  • The number of nodes in the tree is in the range [1, 10^4].
  • -2^31 <= Node.val <= 2^31 - 1
Saved
root =
[2,1,3]