coding•DSA & Problem Solving•Trees & Binary Search Trees
Validate Binary Search Tree
Problem Statement
Given the root of a binary tree, determine if it is a valid binary search tree (BST).
A **valid BST** is defined as follows:
- The left subtree of a node contains only nodes with keys **strictly less than** the node's key.
- The right subtree of a node contains only nodes with keys **strictly greater than** the node's key.
- Both the left and right subtrees must also be binary search trees.
### Constraints
- The number of nodes in the tree is in the range `[1, 10^4]`.
- `-2^31 <= Node.val <= 2^31 - 1`
### Input Format
A single line containing space-separated integers representing the tree in level-order (-1 for null).
### Output Format
Print `true` if the tree is a valid BST, otherwise `false`.
Sample Cases
Example 1Sample Case
Input: 2 1 3
Output: true
Example 2Sample Case
Input: 5 1 4 -1 -1 3 6
Output: false
Example 3Sample Case
Input: -1 -1 1 3 4 5 6
Output: true
Example 4Sample Case
Input: -1 -1 5 6 10 15 20
Output: true
Constraints
Runtime Limit: 2000 ms per test batch
Memory Limit: 256 MB
Standard I/O stream reading
Official submissions are evaluated against hidden test cases on the server to verify time & memory complexity.