Verify BST Integrity

MEDIUM20 pts

Given the root node of a binary tree, determine whether the tree satisfies the structural and ordering properties of a Binary Search Tree (BST).

A valid BST must adhere to the following invariants:

Left Subtree Constraint: Every node in the left subtree of any given node must contain a value strictly less than that node's value.
Right Subtree Constraint: Every node in the right subtree of any given node must contain a value strictly greater than that node's value.
Recursive Validity: Both the left and right subtrees must themselves be valid binary search trees, following the same constraints recursively throughout the entire tree structure.

Your task is to implement a function that examines the tree and returns true if it conforms to all BST properties, or false if any violation exists anywhere in the tree.

Example

Input

root = [2,1,3]

Output

true

Explanation

The root has value 2. Its left child has value 1 (which is less than 2) and its right child has value 3 (which is greater than 2). Both subtrees are valid BSTs with single nodes, so the entire tree is a valid BST.

Example

Input

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

Output

false

Explanation

The root has value 5. While the left child (1) is correctly less than 5, the right child has value 4, which is NOT greater than 5. This violates the BST property, making the entire tree invalid regardless of the structure below.

Example

Input

root = [4,2,6,1,3,5,7]

Output

true

Explanation

This is a perfectly balanced BST. The root (4) has left subtree values {1,2,3} all less than 4, and right subtree values {5,6,7} all greater than 4. Each internal node also satisfies the BST property with respect to its own subtrees.

Accepted0/0·0% Acceptance

Constraints

The number of nodes in the tree is in the range [1, 10⁴].
-2³¹ ≤ Node.val ≤ 2³¹ - 1
Each node contains an integer value.
The tree structure is represented in level-order traversal format.

Code

Visualizer

Solutions

14px

Test Cases3

Results

Submissions

root =

[2,1,3]

Verify BST Integrity

Hints

Verify BST Integrity

Hints