#3MediumTrees· Binary Search Tree Invariants

Validate Binary Search Tree

You are given the `root` of a binary tree. Decide whether it is a **valid binary search tree**. A tree is a valid BST when, for **every** node `x`: - every value in the left subtree of `x` is strictly less than `x.val`, - every value in the right subtree of `x` is strictly greater than `x.val`. The rule applies to whole subtrees, not just to a node's direct children. Equal values are not allowed anywhere in a valid BST. The tree is given as a level-order array: values are listed breadth-first, left to right, and `null` marks a missing child. Children of a missing node are not listed.

Input format

root: level-order array of integers with `null` for missing children

Output format

Boolean: `true` if the tree is a valid BST, otherwise `false`

Examples

Input: root = [8, 4, 12, 2, 6, 10, 14]

Output: true

Every node's left subtree holds smaller values and its right subtree holds larger values.

Input: root = [10, 5, 15, null, null, 6, 20]

Output: false

6 sits in the right subtree of 10 but is smaller than 10, so the tree is not a BST even though 6 < 15 locally.

Input: root = [3, 3]

Output: false

Duplicates are not allowed: the left child must be strictly less than its parent.

Constraints

1 <= number of nodes <= 10^4
-2^31 <= Node.val <= 2^31 - 1

Study first

Trees & Binary Search Trees

#trees
#binary-search-tree
#depth-first-search
#in-order-traversal