Validate Binary Search Tree

Medium

treebinary-search-treedfs

Determine whether a binary tree is a valid binary search tree: every node's left subtree contains only smaller values, its right subtree only larger values, and both subtrees are BSTs.

Input: one line — the tree in level order. Output: true or false.

Example 1

Input:

2 1 3

Output:

true

Example 2

Input:

5 1 4 null null 3 6

Output:

false

3 sits in the right subtree of 5.

Constraints

1 ≤ nodes ≤ 10^4
-2^31 ≤ values ≤ 2^31 − 1

Watch a video walkthrough

Run your code against the sample tests, or Submit to run the full suite.

Problems

Validate Binary Search Tree

Medium

treebinary-search-treedfs

Determine whether a binary tree is a valid binary search tree: every node's left subtree contains only smaller values, its right subtree only larger values, and both subtrees are BSTs.

Input: one line — the tree in level order. Output: true or false.

Example 1

Input:

2 1 3

Output:

true

Example 2

Input:

5 1 4 null null 3 6

Output:

false

3 sits in the right subtree of 5.

Constraints

1 ≤ nodes ≤ 10^4
-2^31 ≤ values ≤ 2^31 − 1

Watch a video walkthrough

Run your code against the sample tests, or Submit to run the full suite.