Validate Binary Search Tree

Given the root of a binary tree, return true if it satisfies the binary search tree property. Pattern focus: BST Validation with Bounds. Carry valid lower and upper bounds while traversing so every subtree respects the BST invariant.

Input Format

root = binary tree root

Output Format

true if the tree is a valid BST

Constraints

  • 1 <= number of nodes <= 10^5
  • -10^9 <= node values <= 10^9
  • root must satisfy the format described in inputFormat.

Examples

Example 1:

Input:

root = [2,1,3]

Output:

true

Explanation:

Every node satisfies the BST ordering rules.

Example 2:

Input:

root = [5,1,4,null,null,3,6]

Output:

false

Explanation:

Node 3 appears in the right subtree of 5 but is smaller than 5.

Loading...
Validate Binary Search Tree - Binary Search Tree