All problems

Validate Binary Search Tree

Medium · tree dfs

You are given the root of a binary tree. Return True if it is a valid binary search tree (BST), and False otherwise.

In a valid BST, every node obeys the rule against its whole subtrees, not just its direct children: all values in the left subtree are strictly smaller than the node, and all values in the right subtree are strictly larger. Equal values are never allowed, so a tree that holds the same number twice is invalid.

An empty tree counts as a valid BST. Node values can be as small as -2^31 and as large as 2^31 - 1, so be careful with any sentinel value you pick for "no limit".

Examples

Example 1

Input: root = [2, 1, 3]

Output: True

1 is smaller than 2 on the left, and 3 is larger than 2 on the right.

Example 2

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

Output: False

4 is the right child of 5 but is smaller than 5, so it breaks the rule right away.

Example 3

Input: root = [5, 4, 6, null, null, 3, 7]

Output: False

Every parent looks fine locally (3 < 6 < 7), but 3 sits in the right subtree of 5 and is smaller than 5.

Constraints